自动搬运

查看原文

来自洛谷，原作者为

	_rqy **

搬运于2025-08-24 22:43:12，当前版本为作者最后更新于2022-11-21 02:33:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

应某同学邀请, 做了一下月赛题. 感觉这题挺有意思, 来写一篇题解.

闲言少叙, 书归正传.

思路

看到这题, 我首先想到分块. 如果把整个值域分成大约 $\sqrt{n}$ 块. 考虑一次修改之后, 有一些区间会大幅度减小, 他们跨过的块的个数会变少. 对于这样的区间, 我们试图快速找到他们, 找到之后暴力修改. 因为每个区间最多被这样修改不超过 $\sqrt{n}$ 次, 所以这个复杂度是对的 (如果我们可以快速找到这样的区间).

接下来考虑哪些区间发生了变化, 但是跨过的块的个数不会变少. 可以发现, 设修改的左右端点是 $L, R$, 那么只有左端点和 $L$ 同块的区间, 或者右端点和 $R$ 同块的区间, 才有可能出现这种情况.

我们先考虑一种简单情况, 那就是 $L, R$ 不处于同一个块, 并且我们只考虑整个区间都在 $L$ 所在块内的区间. 设这个区间是 $[l, r]$, 那么如果 $L \in [l, r]$, 则 $[l, r]$ 会变成 $[L, r]$. 否则 $[l, r]$ 会保持不变.

这似乎并没有什么好办法去维护. 那么暴力修改可不可行呢? 好消息是暴力是可行的!

我们把修改区间看成删除后重新插入. 那么在这一次修改中, 我们只插入了 $O(\sqrt{n})$ 种区间. 如果我们可以把相同的区间合并并计算一个重数, 那么一共只会插入 $O(n\sqrt{n})$ 种区间. (以下假设修改次数与 $n$ 同阶.)

因此如果我们可以快速找到要修改的区间, 那么这一部分修改的总复杂度也在 $O(n\sqrt{n})$.

那么如果考虑任意的左端点在这个块中的区间 $[l, r]$, 我们可以把它暂且当成 $[l, T]$ 来处理, 其中 $T$ 表示这个块的右端点.

这样, 我们还有三个问题:

1. 块间修改的时候, 我们怎么找到修改后跨过的块会减少的区间呢? 可以对每一块维护左端点在这一块内, 右端点不在这一块内的所有区间, 按右端点从大到小维护. 这样我们修改的时候, 只需要找 $L$ 所在块的左边所有块延伸出的区间中, 右端点比 $L$ 更大的即可. 对右端点, 也可以同样处理.
2. 块内修改的时候, 我们怎么找到需要修改的区间呢? 可以对每个 $l$, 把左端点为 $l$ 的块内区间按右端点从小到大挂成链表. 只需要枚举 $l$, 然后在链表里按右端点从大到小遍历所有受到影响的区间即可.
3. 如何维护询问的答案? 这个询问还是比较好处理的. 它相当于说对每个区间, 把整个区间 $+1$. 然后查询区间和. 由于我们所有修改都是暴力修改, 只需要每次暴力修改的时候区间加, 询问的时候区间和即可. 由于这个区间加次数过多, 可以用根号平衡技巧把复杂度优化到 $O(n\sqrt{n})$, 不带 $\log$.

等一下! 如果你试图实现这个算法, 就会发现一个问题. 由于我们在块内修改的时候, 跨过块的区间也会被合并起来一起修改, 在某个端点被修改过后, 我们发现这个区间跨过的块会减少的时候, 就不知道它当前的端点在哪里了!

而且如果一个区间的右端点受块内影响减小了, 那么我们再寻找"右端点比 $L$ 更大的区间"来确定哪些区间会被缩小的时候, 就难以处理了.

好在这也不难解决. 我们可以给修改时新增的区间建立一个结点, 然后让删掉的区间对应的结点指向它, 然后使用并查集就可以了. 上面的两个问题都可以迎刃而解 (第二个问题可以和块内修改一起处理: 只需要把左端点在 $T$, 右端点比 $L$ 更大的那些区间对应的并查集拆出来就得到了).

另一种办法是对每个块, 把处于块内的所有修改的左(右)端点按时间建立单调栈, 然后二分即可 (因为如果某个区间过了很长时间之后, 发现他跨过的块减少了, 那么这个时候考虑它现在的左端点, 一定是上一次跨过的块减少的时候到现在为止, 它的左端点所在的块里所有修改的左端点的最大值. 单调栈可以维护时间后缀的最大值).

而如果使用单调栈, 对于第二个问题, 相当于找到"上一次修改的右端点落在 $L$ 所在块内并且比 $L$ 更靠左"这件事情发生之后所有右端点被放到 $L$ 块内在 $L$ 后面的区间. 这件事情的发生时间仍然可以二分出来, 然后我们需要一个动态的三维数点 (动态三维数点!), 可以搞个主席树...这个做法我并没有想到足够好的优化方法, 所以没有写出代码. 如果有人可以提供优化方法可以联系我.

那么, 这个思路能不能优化到 $O(n \times \mathrm{poly}(\log n))$ 呢? 答案是可以的. 我们发现上面的分块完全可以嵌套: 我们把跨过块的单独处理, 块内的递归处理, 那么这完全可以改到线段树上! 最后的复杂度即为 $O(n \log^2 n)$, 因为每次变更区间时需要 $O(\log n)$ 的树状数组修改, 还需要用堆维护区间.

呜呜.

代码

#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <cctype>
#include <cstdio>
#include <cstring>

typedef long long LL;
const int N = 200050;
const int M = 100050;

int read() {
  int ans = 0, c;
  while (!isdigit(c = getchar()));
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans;
}

namespace UFS {
  const int MM = M * 200;
  int Fa[MM], cnt = 0; // 正: 父亲; 负: 子树大小
  int Ls[MM], Rb[MM], id[MM];
  int sz[MM];
  int pos[MM];

  int Find(int x) { return Fa[x] < 0 ? x : Fa[x] = Find(Fa[x]); }
  int Union(int x, int y) {
    x = Find(x); y = Find(y);
    if (Fa[x] < Fa[y]) // y 子树更大
      std::swap(x, y);
    sz[x] += sz[y];
    Fa[x] += Fa[y]; Fa[y] = x;
    Rb[y] = Ls[x]; Ls[x] = y;
    return x;
  }

  int corNode[M * 2];

  inline int addNode(int i, int p) {
    int o = cnt++;
    if (cnt % 10000 == 0) fprintf(stderr, "qwq %d\n", cnt);
    if (i >= 0) {
      id[o] = i;
      corNode[i] = o;
      sz[o] = 1;
    } else {
      id[o] = -1;
      sz[o] = 0;
    }
    pos[o] = p;
    Fa[o] = -1;
    Ls[o] = Rb[o] = -1;
    return o;
  }

  inline void rmNode(int i) {
    int x = corNode[i];
    --sz[Find(x)];
    id[x] = -1;
  }
}

typedef std::pair<int, int> E;
#define mp std::make_pair

const int NN = N * 3; // TODO

std::priority_queue<E, std::vector<E>, std::greater<E>> LE[NN];
std::priority_queue<E> RE[NN];

inline void addA(int l, int r, LL v);

// 线段树是"左闭右开"区间
void addE(int o, int l, int r, int k, int L, int R) {
  int m = (l + r) / 2;
  if (R < m) addE(o << 1, l, m, k, L, R);
  else if (L > m) addE(o << 1 | 1, m, r, k, L, R);
  else {
    LE[o].push(mp(L, UFS::addNode(k << 1, L)));
    RE[o].push(mp(R, UFS::addNode(k << 1 | 1, R)));
  }
}

void reAddE(int x, int l1, int o, int l, int r, int Lq, int Rq) {
  using namespace UFS;
  int t = id[x];
  if (t >= 0) {
    int k = t >> 1, y = corNode[t ^ 1];
    int Lp = l1, Rp = pos[Find(y)];
    if (t & 1) std::swap(Lp, Rp);
    rmNode(t); rmNode(t ^ 1);

    int Ls = std::max(Lp, Lq), Rs = std::min(Rp, Rq);
    if (Ls == Rs) {
      addA(Lp, Rp, -1);
#ifdef DEBUG
      fprintf(stderr, "Remove the range [%d, %d]\n", Lp, Rp);
#endif
    } else {
#ifdef DEBUG
      fprintf(stderr, "Change the range [%d, %d] to [%d, %d]\n", Lp, Rp, Ls, Rs);
#endif
      if (Ls > Lp) addA(Lp, Ls, -1);
      if (Rs < Rp) addA(Rs, Rp, -1);
      addE(o, l, r, k, Ls, Rs);
    }
  }
  for (int y = Ls[x]; y >= 0; y = Rb[y])
    reAddE(y, l1, o, l, r, Lq, Rq);
}

void modify(int o, int l, int r, int Lq, int Rq) {
  if (r - l == 1 || r < Lq || l > Rq || (l >= Lq && r <= Rq)) return;
#ifdef DEBUG
      fprintf(stderr, "> %d %d %d\n", o, l, r);
#endif
  int m = (l + r) / 2;
  if (Rq < m) {
    while (!LE[o].empty()) {
      E x = LE[o].top();
      if (x.first > Rq) break;
      LE[o].pop();
      reAddE(x.second, x.first, o << 1, l, m, Lq, Rq);
    }
    modify(o << 1, l, m, Lq, Rq);
  } else if (Lq > m) {
    while (!RE[o].empty()) {
      E x = RE[o].top();
      if (x.first < Lq) break;
      RE[o].pop();
      reAddE(x.second, x.first, o << 1 | 1, m, r, Lq, Rq);
    }
    modify(o << 1 | 1, m, r, Lq, Rq);
  } else {
    using namespace UFS;
    int nd = addNode(-1, Lq);
    while (!LE[o].empty()) {
      E x = LE[o].top();
      if (x.first > Lq) break;
      LE[o].pop();
#ifdef DEBUG
      fprintf(stderr, "Modify the left endpoint of %d ranges from %d to %d\n",
              UFS::sz[x.second], x.first, Lq);
#endif
      addA(x.first, Lq, -UFS::sz[x.second]);
      nd = Union(nd, x.second);
    }
    pos[nd] = Lq;
    LE[o].push(mp(Lq, nd));
    nd = addNode(-1, Rq);
    while (!RE[o].empty()) {
      E x = RE[o].top();
      if (x.first < Rq) break;
      RE[o].pop();
#ifdef DEBUG
      fprintf(stderr, "Modify the right endpoint of %d ranges from %d to %d\n",
              UFS::sz[x.second], x.first, Rq);
#endif
      addA(Rq, x.first, -UFS::sz[x.second]);
      nd = Union(nd, x.second);
    }
    pos[nd] = Rq;
    RE[o].push(mp(Rq, nd));
    modify(o << 1, l, m, Lq, Rq);
    modify(o << 1 | 1, m, r, Lq, Rq);
  }
}

LL A[N], B[N];

void adda(LL *A, int x, LL v) {
  for (; x < N; x += x & -x)
    A[x] += v;
}

inline void addA(int l, int r, LL v) {
  // 区间加 v
  adda(B, r, -v); adda(B, l, v);
  adda(A, r, v * r); adda(A, l, -v * l);
}

LL querya(LL *A, int x) {
  LL ans = 0;
  for (; x; x -= x & -x)
    ans += A[x];
  return ans;
}

inline LL queryA(int l, int r) {
  return r * querya(B, r) + querya(A, r) - l * querya(B, l) - querya(A, l);
}

int main() {
  int q = read(), type = read();
  LL last = 0;
  int t = 0;
  while (q--) {
    int k = read(), l = read(), r = read();
    l = (l + type * last) % 200001;
    r = (r + type * last) % 200001;
    if (k == 1) {
      if (l < r) {
        addA(l, r, 1);
        addE(1, 1, 200000, t++, l, r);
      }
    } else if (k == 2) {
      modify(1, 1, 200000, l, r);
    } else {
      printf("%lld\n", last = queryA(l, r));
    }
  }
}