月赛题 P8861 题解
应某同学邀请, 做了一下月赛题. 感觉这题挺有意思, 来写一篇题解.
闲言少叙, 书归正传.
思路
看到这题, 我首先想到分块. 如果把整个值域分成大约
接下来考虑哪些区间发生了变化, 但是跨过的块的个数不会变少.
可以发现, 设修改的左右端点是
我们先考虑一种简单情况, 那就是
这似乎并没有什么好办法去维护. 那么暴力修改可不可行呢? 好消息是暴力是可行的!
我们把修改区间看成删除后重新插入.
那么在这一次修改中, 我们只插入了
因此如果我们可以快速找到要修改的区间, 那么这一部分修改的总复杂度也在
那么如果考虑任意的左端点在这个块中的区间
这样, 我们还有三个问题:
- 块间修改的时候, 我们怎么找到修改后跨过的块会减少的区间呢?
可以对每一块维护左端点在这一块内, 右端点不在这一块内的所有区间,
按右端点从大到小维护.
这样我们修改的时候, 只需要找
L 所在块的左边所有块延伸出的区间中, 右端点比L 更大的即可. 对右端点, 也可以同样处理. - 块内修改的时候, 我们怎么找到需要修改的区间呢?
可以对每个
l , 把左端点为l 的块内区间按右端点从小到大挂成链表. 只需要枚举l , 然后在链表里按右端点从大到小遍历所有受到影响的区间即可. - 如何维护询问的答案? 这个询问还是比较好处理的.
它相当于说对每个区间, 把整个区间
+1 . 然后查询区间和. 由于我们所有修改都是暴力修改, 只需要每次暴力修改的时候区间加, 询问的时候区间和即可. 由于这个区间加次数过多, 可以用根号平衡技巧把复杂度优化到O(n\sqrt{n}) , 不带\log .
等一下! 如果你试图实现这个算法, 就会发现一个问题. 由于我们在块内修改的时候, 跨过块的区间也会被合并起来一起修改, 在某个端点被修改过后, 我们发现这个区间跨过的块会减少的时候, 就不知道它当前的端点在哪里了!
而且如果一个区间的右端点受块内影响减小了, 那么我们再寻找"右端点比
好在这也不难解决. 我们可以给修改时新增的区间建立一个结点, 然后让删掉的区间对应的结点指向它, 然后使用并查集就可以了. 上面的两个问题都可以迎刃而解 (第二个问题可以和块内修改一起处理: 只需要把左端点在
另一种办法是对每个块, 把处于块内的所有修改的左(右)端点按时间建立单调栈, 然后二分即可 (因为如果某个区间过了很长时间之后, 发现他跨过的块减少了, 那么这个时候考虑它现在的左端点, 一定是上一次跨过的块减少的时候到现在为止, 它的左端点所在的块里所有修改的左端点的最大值. 单调栈可以维护时间后缀的最大值).
而如果使用单调栈, 对于第二个问题, 相当于找到"上一次修改的右端点落在
那么, 这个思路能不能优化到
呜呜.
代码
#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));
}
}
}