P9083 [PA 2018] Ryki 题解

Description

想象世界的某处存在这样一个二维平面，其上有 $n$ 个人，其中有 $n-1$ 个是三角初音，剩下一个是三角初华。第 $i$ 个人在整点 $(x_i,y_i)$ 。

在接下来的 $n$ 天中，第 $i$ 天，如果第 $i$ 个人是三角初音，则她会大喊“小祥……小祥……”，然后其她所有三角初音都会在横、纵坐标上分别靠近其 $1$ 个单位。具体地，对于第 $j$ 个人，若其也为三角初音，且 $x_i\not=x_j$ ，则会有 $x_j\gets x_j+\frac{|x_i-x_j|}{x_i-x_j}$ ， $y_j$ 同理。

但是你分辨不出来这 $n$ 个人里哪个是三角初华，哪些是三角初音。于是，对于每个 $k$ ，你都需要求出若第 $k$ 个人为三角初华，在第 $n$ 天之后，所有人的横纵坐标之积的和，即最终的 $\sum_{i=1}^nx_i\times y_i$ 。

$n\leq 2.5\times 10^5,x_i,y_i\leq 10^6$ 。

Solution

首先 $x,y$ 两维互相独立，这里先只考虑 $x$ 。由于任意时刻点之间的先后顺序不变，所以先排序。

设 $x'_i$ 表示没有任何一个人是三角初华的情况下 $i$ 最后的 $x$ 坐标。如果存在三角初华，容易归纳证明存在 $[l,r]$ ，满足 $x_i=x'_i-[i<l]+[i>r]$ 。

考虑求出每个点的 $l_i$ 和 $r_i$ 。

先从前往后扫 $i$ ，每次对原序列做中心为 $i$ 的聚拢操作，并更新所有 $j<i$ 的 $l_j,r_j$ 。

把序列排序后的极长相等连续段拿出来，设 $[L,R]$ 为 $i$ 所在的连续段。

显然此时 $l_i=L,r_i=R$ ，因为本次如果要操作，不在区间内的都会变，而现在没有变化。

然后有个结论：任何时刻的任意 $[l_j,r_j]$ 都一定在 $j$ 所处的连续段内，这个可以通过后面的做法归纳证明。

如果 $j\notin[L,R]$ ，不妨设 $j<L$ ，由于 $[r_j+1,n]$ 这部分是整体平移，所以这部分的变化量和 $j$ 不是初华是一样的，而前面的显然一直都是整体向右平移一步，没有影响，所以 $[l_j,r_j]$ 不变。 $j>R$ 同理。

如果 $j\in[L,R]$ ，这里需要继续分类讨论：

$r_j<i$ ，此时 $[r_j+1,R]$ 不会动，而 $[L,r_j]$ 会向右平移，所以 $[l_j,r_j]$ 会和 $[r_j+1,R]$ 合并，所以 $[l_j,r_j]$ 会比原先多 $1$ ，同时 $[1,L-1]$ 本来也会加，所以 $[l_j,r_j]$ 变为 $[L,l_j-1]$ 。
$l_j>r$ ，变为 $[r_j+1,R]$ 。
$i\in [l_j,r_j]$ ，此时 $[L,l_j-1]$ 和 $[r_j+1,R]$ 会和 $[l_j,r_j]$ 合并，所以变为 $[L,R]$ 。

观察上述变化过程，可以发现任意时刻的区间一定可以看成是很多个不交的极长区间 $[L_i,R_i]$ ，其余区间一定是左端点或者右端点挂在这些极长区间的形式。

考虑用链表和维护这些挂在极长区间的区间，即维护二元组 $(x,v)$ 表示在并查集上编号为 $x$ 的点的集合，不同于极长区间端点的另一端点为 $v$ 。

同时也可以用链表维护这些极长区间，修改时分讨一下即可，具体见代码。

这部分时间复杂度是 $O(n)$ 。

剩下的部分是简单的二维数点，可以做到 $O(n\log n)$ 。

总时间复杂度： $O(n\log n)$ 。

Code

#include <bits/stdc++.h>

// #define int int64_t

namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
inline char getc() {
  return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
  x = 0; int f = 0; char ch = getc();
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
  while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
  x = (f ? -x : x); return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }
 
char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
inline void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
  if (!x) putc('0');
  if (x < 0) x = -x, putc('-');
  char c[40]; int tot = 0;
  while (x) c[++tot] = x % 10, x /= 10;
  for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
void write(char *x) { while (*x) putc(*x++); }
void write(const char *x) { while (*x) putc(*x++); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::read; using FASTIO::putc; using FASTIO::write;

using i64 = int64_t;
using i128 = __int128_t;
using pii = std::pair<int, int>;

const int kMaxN = 2e6 + 5, kMod = 1e9 + 7;

int n;
int x[kMaxN], y[kMaxN], rkx[kMaxN], rky[kMaxN], tx[kMaxN], ty[kMaxN];
int idx[kMaxN], idy[kMaxN], lx[kMaxN], rx[kMaxN], ly[kMaxN], ry[kMaxN];
int ans[kMaxN];
std::vector<int> qq[kMaxN];

int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

struct BIT {
  int c[kMaxN];
  void upd(int x, int v) {
    for (; x <= n; x += x & -x) c[x] += v;
  }
  int qry(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret += c[x];
    return ret;
  }
} bit;

struct DSU {
  int fa[kMaxN];
  void init(int n) { std::iota(fa + 1, fa + 1 + n, 1); }
  int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
  int unionn(int x, int y) {
    int fx = find(x), fy = find(y);
    if (!x || !y) return fx + fy;
    return fa[fx] = fy;
  }
} seq, dsu;

// seq 维护序列上的连续段，dsu 维护相等的

struct List {
  int cnt, nxt[kMaxN * 3];
  pii p[kMaxN * 3];
  void init() { cnt = 0; }
  int newnode(pii v) {
    if (!v.first) return 0;
    assert(v.second);
    p[++cnt] = v, nxt[cnt] = 0;
    return cnt;
  }
} list;

struct Node {
  int h, t;
  Node(int _h = 0) { h = t = _h; }
  Node(int _h, int _t) { h = _h, t = _t; }
  void init(int id = 0) { h = t = id; }
} L[kMaxN], R[kMaxN];

void merge(Node &a, Node b) {
  if (!a.h) return void(a = b);
  if (!b.h) return;
  list.nxt[a.t] = b.h, a.t = b.t;
}

int unionn(Node a, int x = 0) {
  int id = x;
  for (int i = a.h; i; i = list.nxt[i]) {
    id = dsu.unionn(id, list.p[i].first);
  }
  return id;
}

void solve(int n, int *x, int *rk, int *id, int *t, int *l, int *r) {
  static int diff[kMaxN], idx[kMaxN], nxt[kMaxN];
  static int ll[kMaxN], rr[kMaxN];
  std::iota(id + 1, id + 1 + n, 1);
  std::sort(id + 1, id + 1 + n, [&] (int i, int j) { return x[i] < x[j]; });
  list.init(), seq.init(n), dsu.init(n);
  for (int i = 1; i <= n; ++i) {
    rk[id[i]] = i, L[i].init(), R[i].init();
    diff[i] = x[id[i]] - x[id[i - 1]];
    if (!diff[i]) seq.unionn(i, i - 1);
    nxt[i] = i + 1, ll[i] = rr[i] = idx[i] = 0;
  }
  diff[n + 1] = 1e9, nxt[0] = 1;
  for (int i = 1; i <= n; ++i) {
    int s = seq.find(rk[i]), id = i;
    L[0].init(), R[0].init();
    for (int j = s; j == s || !diff[j]; j = nxt[j]) {
      nxt[s] = nxt[j];
      if (nxt[j] <= rk[i]) {
        merge(L[0], R[j]), merge(L[0], Node(list.newnode({unionn(L[j], idx[j]), j})));
      } else if (j > rk[i]) {
        merge(R[0], L[j]), merge(R[0], Node(list.newnode({unionn(R[j], idx[j]), nxt[j]})));
      } else {
        int idl = 0, idr = 0;
        id = dsu.unionn(id, idx[j]);
        for (int k = L[j].h; k; k = list.nxt[k]) {
          if (list.p[k].second <= rk[i]) idl = dsu.unionn(idl, list.p[k].first);
          else id = dsu.unionn(id, list.p[k].first);
        }
        for (int k = R[j].h; k; k = list.nxt[k]) {
          if (list.p[k].second > rk[i]) idr = dsu.unionn(idr, list.p[k].first);
          else id = dsu.unionn(id, list.p[k].first);
        }
        if (idl) merge(L[0], Node(list.newnode({idl, j})));
        if (idr) merge(R[0], Node(list.newnode({idr, nxt[j]})));
      }
    }
    L[s] = L[0], R[s] = R[0], idx[s] = id;
    // merge(R[s], Node(list.newnode({id, s})));
    // merge(L[s], Node(list.newnode({id, nxt[s]})));
    ++diff[1];
    if (!--diff[s]) seq.unionn(s, s - 1);
    if (!--diff[nxt[s]]) seq.unionn(nxt[s], nxt[s] - 1);
    // merge(R[s], Node(list.newnode({i, seq.find(rk[i])})));
  }
  // std::cerr << dsu.find(6) << '\n';
  for (int i = 1; i <= n; i = nxt[i]) {
    // std::cerr << i << ' ';
    ll[idx[i]] = i, rr[idx[i]] = nxt[i] - 1;
    // if (nxt[i] - 1 == 92) std::cerr << idx[i] << ' ' << i << ' ' << ll[idx[i]] << '\n';
    for (int j = L[i].h; j; j = list.nxt[j]) {
      // if (list.p[j].first == 6) std::cerr << i << ' ' << nxt[i] - 1 << '\n';
      ll[list.p[j].first] = i, rr[list.p[j].first] = list.p[j].second - 1;
    }
    for (int j = R[i].h; j; j = list.nxt[j]) {
      // if (list.p[j].first == 6) std::cerr << i << ' ' << list.p[j].second << ' ' << nxt[i] - 1 << '\n';
      ll[list.p[j].first] = list.p[j].second, rr[list.p[j].first] = nxt[i] - 1;
    }
  }
  // std::cerr << '\n';
  for (int i = 1; i <= n; ++i) l[i] = ll[dsu.find(i)], r[i] = rr[dsu.find(i)];
  for (int i = 1; i <= n; ++i) t[id[i]] = (diff[i] += diff[i - 1]);
}

void getans() {
  for (int i = 1; i <= n; ++i) {
    bit.upd(rky[idx[i]], 1);
    for (auto j : qq[i]) dec(ans[j], sub(sub(i, bit.qry(ry[j])), bit.qry(ly[j] - 1)));
  }
}

void dickdreamer() {
  read(n);
  for (int i = 1; i <= n; ++i) read(x[i], y[i]);
  solve(n, x, rkx, idx, tx, lx, rx);
  solve(n, y, rky, idy, ty, ly, ry);
  static int sumx[kMaxN], sumy[kMaxN];
  int sumxy = 0;
  for (int i = 1; i <= n; ++i) {
    sumx[i] = add(sumx[i - 1], tx[idy[i]]);
    sumy[i] = add(sumy[i - 1], ty[idx[i]]);
    inc(sumxy, 1ll * tx[i] * ty[i] % kMod);
  }
  // for (int i = 1; i <= n; ++i) std::cout << tx[i] << ' ' << lx[i] << ' ' << rx[i] << '\n';
  // for (int i = 1; i <= n; ++i) std::cout << ty[i] << ' ' << ly[i] << ' ' << ry[i] << '\n';
  for (int i = 1; i <= n; ++i) {
    // int ans = 1ll * x[i] * y[i] % kMod;
    inc(ans[i], sumxy);
    inc(ans[i], sub(sub(sumx[n], sumx[ry[i]]), sumx[ly[i] - 1]));
    inc(ans[i], sub(sub(sumy[n], sumy[rx[i]]), sumy[lx[i] - 1]));
    inc(ans[i], sub(n - ry[i], ly[i] - 1));
    // for (int j = 1; j <= n; ++j) {
    //   // inc(ans[i], 1ll * ((j > rx[i]) - (j < lx[i])) * ((rky[idx[j]] > ry[i]) - (rky[idx[j]] < ly[i])) % kMod);
    //   if (j <= rx[i]) dec(ans[i], (rky[idx[j]] > ry[i]) - (rky[idx[j]] < ly[i]));
    //   if (j <= lx[i] - 1) dec(ans[i], (rky[idx[j]] > ry[i]) - (rky[idx[j]] < ly[i]));
    // }
    dec(ans[i], 1ll * (tx[i] + (rkx[i] > rx[i]) - (rkx[i] < lx[i])) * (ty[i] + (rky[i] > ry[i]) - (rky[i] < ly[i])) % kMod);
    inc(ans[i], 1ll * x[i] * y[i] % kMod);
    qq[lx[i] - 1].emplace_back(i), qq[rx[i]].emplace_back(i);
    // write(ans[i], '\n');
  }
  getans();
  for (int i = 1; i <= n; ++i) write(ans[i], '\n');
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

P9083 [PA 2018] Ryki 题解

https://sobaliuziao.github.io/2025/05/13/post/dd025f35.html

作者

Egg_laying_master

发布于

2025年5月13日

许可协议

P12546 [UOI 2025] Convex Array 题解上一篇

CF2092F Andryusha and CCB 题解下一篇