有趣 ds 题。
首先有一个部分分 \(l_i \le 10^5 \le r_i\)。发现这相当于可以把区间分成左右两部分，那么我们可以考虑将左右分开考虑。
我们将每个区间拆开成两部分，这样插入的时候就直接插入即可，修改操作时，发现实际上就是将左端所有长度大于 \(10^5 - l\) 的区间长度改为 \(10^5 - l\)，右端同理。容易发现这个是可以暴力做的，我们把长度相同的区间并查集缩起来，这样我们可以用一个堆来维护左右端，每次暴力弹出对顶元素，把它们缩起来。容易发现均摊复杂度是正确的。查询的操作实际上就是一个区间求和，所以直接拿树状数组顺便维护一下区间和即可。
那么拓展到一般情况，可以想到类似于分治的东西，即可通过上述方法覆盖到所有的区间。我们用线段树维护这个东西。
插入时，将一个区间插入到包含它且穿过中点的区间上。
修改时，考虑分几种情况：
- 如果修改区间完全包含这个区间，那么显然不会有影响，直接返回；
- 如果修改区间恰好穿过当前区间的中点，那么用上述的方法维护即可；
- 如果修改区间完全包含在左区间或右区间，那么就把所有与当前修改区间相交的区间拿出来，取交之后重新插入左区间或右区间。发现，每一个区间最多会被这样插入 \(O(\log n)\) 次，所以这里均摊复杂度也是对的。
总复杂度 \(O(n \log^2 n)\)。
具体实现上，我们需要记录左端的每个点与右端对应的点，删除时可以给两个点打一个删除标记；为了遍历一个并查集中的所有数，我们同时需要维护一个链表，链表容易遍历与合并。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005, MAXM = MAXN * 120;
int q, type;
long long lstans;
struct UnionFindSet {
int fa[MAXM], siz[MAXM], tot;
int cnt[MAXM], id[MAXM], pt[MAXM];
int ed[MAXM], nxt[MAXM];
int pos[MAXM];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int newNode(int k, int p) {
int u = ++tot;
fa[u] = ed[u] = u, siz[u] = cnt[u] = 1, pt[k] = u, id[u] = k, pos[u] = p;
return u;
}
void delNode(int u) {
if (id[u]) id[u] = 0, cnt[find(u)]--;
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (siz[x] > siz[y]) swap(x, y);
fa[x] = y, siz[y] += siz[x], cnt[y] += cnt[x];
nxt[ed[y]] = x, ed[y] = ed[x];
return y;
}
} ufs;
struct BinaryIndexTree {
long long a[MAXN], b[MAXN];
#define lowbit(x) (x & (-x))
void add(long long *a, int d, long long v) {
while (d < MAXN) {
a[d] += v;
d += lowbit(d);
}
}
long long query(long long *a, int d) {
long long ret = 0;
while (d) {
ret += a[d];
d -= lowbit(d);
}
return ret;
}
void add(int d, long long v) {
add(a, d, v), add(b, d, d * v);
}
void add(int a, int b, long long v) {
add(a, v), add(b, -v);
}
long long query(int l, int r) {
return (r * query(a, r) - query(b, r)) - (l * query(a, l) - query(b, l));
}
} bit;
struct SegmentTree {
struct Node {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> l;
priority_queue<pair<int, int>> r;
} t[MAXN << 3];
#define lc (i << 1)
#define rc (i << 1 | 1)
void addEdge(int a, int b, int k, int i = 1, int l = 1, int r = 200000) {
if (l == r) return;
int mid = (l + r) >> 1;
if (b < mid) return addEdge(a, b, k, lc, l, mid);
if (a > mid) return addEdge(a, b, k, rc, mid, r);
t[i].l.push({ a, ufs.newNode(k << 1, a) });
t[i].r.push({ b, ufs.newNode(k << 1 | 1, b) });
bit.add(a, b, 1);
}
void update(int a, int b, int i = 1, int l = 1, int r = 200000) {
if (r - l == 1 || a <= l && r <= b) return;
int mid = (l + r) >> 1;
if (b < mid) {
while (t[i].l.size()) {
auto p = t[i].l.top();
if (p.first > b) break;
t[i].l.pop();
int x = p.second;
do {
if (ufs.id[x]) {
int y = ufs.id[x];
ufs.delNode(x), ufs.delNode(ufs.pt[y ^ 1]);
bit.add(ufs.pos[ufs.find(x)], ufs.pos[ufs.find(ufs.pt[y ^ 1])], -1);
addEdge(max(a, p.first), b, y / 2, lc, l, mid);
}
} while (x = ufs.nxt[x]);
}
update(a, b, lc, l, mid);
} else if (a > mid) {
while (t[i].r.size()) {
auto p = t[i].r.top();
if (p.first < a) break;
t[i].r.pop();
int x = p.second;
do {
if (ufs.id[x]) {
int y = ufs.id[x];
ufs.delNode(x), ufs.delNode(ufs.pt[y ^ 1]);
bit.add(ufs.pos[ufs.find(ufs.pt[y ^ 1])], ufs.pos[ufs.find(x)], -1);
addEdge(a, min(p.first, b), y / 2, rc, mid, r);
}
} while (x = ufs.nxt[x]);
}
update(a, b, rc, mid, r);
} else {
{
int x = 0;
while (t[i].l.size()) {
auto p = t[i].l.top();
if (p.first > a) break;
bit.add(p.first, a, -ufs.cnt[p.second]);
x = ufs.merge(x, p.second);
t[i].l.pop();
}
if (x) {
t[i].l.push({ a, x });
ufs.pos[x] = a;
}
}
{
int x = 0;
while (t[i].r.size()) {
auto p = t[i].r.top();
if (p.first < b) break;
bit.add(b, p.first, -ufs.cnt[p.second]);
x = ufs.merge(x, p.second);
t[i].r.pop();
}
if (x) {
t[i].r.push({ b, x });
ufs.pos[x] = b;
}
}
update(a, b, lc, l, mid), update(a, b, rc, mid, r);
}
}
} st;
int main() {
scanf("%d%d", &q, &type);
int ecnt = 0;
while (q--) {
int op, l, r; scanf("%d%d%d", &op, &l, &r);
l = (l + lstans * type) % 200001, r = (r + lstans * type) % 200001;
if (op == 1) st.addEdge(l, r, ++ecnt);
if (op == 2) st.update(l, r);
if (op == 3) printf("%lld\n", lstans = bit.query(l, r));
}
return 0;
}