题目链接：Problem - 7185 (hdu.edu.cn)

$hdu$ 不支持结构化绑定，悲（

题目描述

给定 $n$ 个砖块，每个砖块初始权值为 $0$ ，颜色相同， $q$ 次操作。

  • 操作 $1$ ，选取一段区间$[l,r]$，让其染上新的未出现过的颜色
  • 操作 $2$ ，将第 $x$ 块砖的颜色染到第 $y$ 块砖所在的连通块上（与第 $y$ 块砖相连且颜色相同）
  • 操作 $3$ ，将与第 $x$ 块砖颜色相同的砖的权值增加 $v$
  • 操作 $4$ ，查询第 $x$ 块砖的权值

思路

首先 $3 \leq n \leq 10^8$ 就直接限制了很多做法，注意到 $q \leq 10^5$，我们染上的颜色数最多也就 $q$ 个，操作的区间最多也就 $q$ 个。

我们考虑用珂朵莉树来维护所有的区间以及该区间的颜色，并且颜色相同且相邻的区间我们要将它们合并成一个区间，对应了操作 $2$ 里的最大连通块。对于操作 $1$ ，我们直接将 $[l,r]$ 进行分裂，然后再将这个区间存入珂朵莉树。我们再用一个数组 $col$ 来记录每个颜色的增量，并用动态开点线段树来维护每个点的权值。对于操作 $2$ 里的染色操作，我们将 $y$ 这一整个连通块的权值增加 $col_y - col_x$ ，意为将原先 $y$ 已经产生的增量加上，因为之后的颜色就变成 $x$ 的颜色了，不再需要这个增量了，然后将之前 $x$ 产生的增量减去，表示染色之后的 $y$ 的连通块对于 $x$ 的颜色的增量为 $-col_x$ ，互不相欠嘛。对于操作 $3$ ，我们直接将 $x$ 所属的颜色的增量 $col+v$ 。对于操作 $4$ ，查询线段树上对应的 $x$ 位置的权值加上 $x$ 所属的颜色增量即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

int n, q;
int ls[N << 6], rs[N << 6], tot, rt;
LL sum[N << 6], lz[N << 6];
void push_down(int x) {
    if (!lz[x]) {
        return;
    }
    if (!ls[x]) {
        ls[x] = ++ tot;
    }
    sum[ls[x]] += lz[x];
    lz[ls[x]] += lz[x];
    if (!rs[x]) {
        rs[x] = ++ tot;
    }
    sum[rs[x]] += lz[x];
    lz[rs[x]] += lz[x];
    lz[x] = 0;
}
void modify(int &x, int l, int r, int ql, int qr, LL v) {
    if (ql > qr || ql > r || qr < l) {
        return;
    }
    if (!x) {
        x = ++ tot;
    }
    if (ql <= l && r <= qr) {
        sum[x] += v;
        lz[x] += v;
        return;
    }
    push_down(x);
    int mid = (l + r) >> 1;
    modify(ls[x], l, mid, ql, qr, v);
    modify(rs[x], mid + 1, r, ql, qr, v);
}
LL query(int x, int l, int r, int p) {
    if (!x) {
        return 0;
    }
    if (l == r) {
        return sum[x];
    }
    push_down(x);
    int mid = (l + r) >> 1;
    if (p <= mid) {
        return query(ls[x], l, mid, p);
    }
    return query(rs[x], mid + 1, r, p);
}
struct Node {
    int l, r;
    mutable int v;
    bool operator < (const Node &o) const {
        return l < o.l;
    }
};
set< Node > odt;
LL col[N];
set< Node >::iterator split(int x) {
    if (x > n) {
        return odt.end();
    }
    auto it = prev(odt.upper_bound({x, 0, 0}));
    if (it->l == x) {
        return it;
    }
    //auto [l, r, v] = *it;
    int l = it->l, r = it->r, v = it->v;
    odt.erase(it);
    odt.insert({l, x - 1, v});
    return odt.insert({x, r, v}).first;
}
void assign(int l, int r, int v) {
    auto R = split(r + 1), L = split(l);
    while (L != odt.begin() && prev(L)->v == v) {
        L = prev(L);
        l = L->l;
    }
    while (R != odt.end() && R->v == v) {
        r = R->r;
        R = next(R);
    }
    for (auto x = L; x != R; ++ x) {
        modify(rt, 1, n, x->l, x->r, col[x->v] - col[v]);
    }
    odt.erase(L, R);
    odt.insert({l, r, v});
}
void solve() {
    cin >> n >> q;
    for (int i = 1; i <= tot; ++ i) {
        ls[i] = rs[i] = sum[i] = lz[i] = 0;
    }
    tot = rt = 0;
    fill(col, col + q + 1, 0);
    odt.clear();
    odt.insert({1, n, 0});
    LL lastans = 0;
    for (int i = 1; i <= q; ++ i) {
        int op, x, y, c, v;
        cin >> op;
        if (op == 1) {
            cin >> x >> c;
            x = ((x - 1) ^ lastans) % n + 1;
            c = ((c - 1) ^ lastans) % ((n - 1) / 2) + 1;
            int l = max(1, x - c), r = l + 2 * c;
            if (r > n) {
                l = n - c * 2, r = n;
            }
            assign(l, r, i);
        } else if (op == 2) {
            cin >> x >> y;
            x = ((x - 1) ^ lastans) % n + 1;
            y = ((y - 1) ^ lastans) % n + 1;
            auto fx = prev(odt.upper_bound({x, 0, 0})), fy = prev(odt.upper_bound({y, 0, 0}));
            if (fx->v != fy->v) {
                assign(fy->l, fy->r, fx->v);
            }
        } else if (op == 3) {
            cin >> x >> v;
            x = ((x - 1) ^ lastans) % n + 1;
            auto fx = prev(odt.upper_bound({x, 0, 0}));
            col[fx->v] += v;
        } else {
            cin >> x;
            x = ((x - 1) ^ lastans) % n + 1;
            auto fx = prev(odt.upper_bound({x, 0, 0}));
            cout << (lastans = query(rt, 1, n, x) + col[fx->v]) << '\n';
            lastans &= 1073741823;
        }
    }
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;
    while (t -- ) {
        solve();
    }
    return 0;
}