![[中山OI2011]小W的问题 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180305b-595x400.png)
[中山OI2011]小W的问题 题解
题目地址：BZOJ：Problem 2441. — [中山市选2011]小W的 …
标签： 线段树
![[SPOJ-COT]Count on a tree 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180226b-1-760x400.png)
可持久化线段树（含主席树）原理与实现
概述
可持久化线段树是一类线段树的实现方式，用于保存线段树的历史版本。本文后半部分所介绍的一种用法是主席树这一类可持久化线段树。主席树是以下标为时间加入元素的一类可持久化线段树，常见的用法是静态查询区间第k大值。下面我们介绍它的原理和实现。
原理
什么叫“可持久”？
可持久的意思是保存历史版本，可以查询到历史操作的结果。比如，对于一个序列进行更改，你可以选择每一次更改前将上次更改后的序列复制一份，再在新序列中更改，以保留这个序列的所有历史版本。同样地，你也可以建一堆线段树来保留线段树的历史版本。但是，这样做的空间是O(Q * 4N)的，显然很难接受，因此我们要使用可持久化线段树这种实现方法。
结构
一棵可持久化线段树的结构如图所示。
如图，黑色的为最初版本的线段树，蓝色的为版本2。
修改
如示例图所示，线段树的修改应该是修改一条链，也就是两个相邻版本的的线段树只会有一条链有差别。那我们考虑动态开点，将后面版本的线段树那些没有更改的儿子指向前一个版本的线段树的节点，这样每次只会新建一条链的节点，空间降低为O(4N + Q \log N)，是可以接受的了。
查询
每次修改后存储这一次修改的新线段树的根，然后按照根下去正常查询即可。
实现
修改
每次修改前令本次的根为上一次的根，再执行下面的操作。
inline void insert(int &o, int l, int r, int x) {
tree[++tot] = tree[o];
o = tot;
tree[o].val++;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) insert(tree[o].lch, l, mid, x);
else insert(tree[o].rch, mid + 1, r, x);
}
查询
常规操作，不提供实现细节。
主席树（查询区间k小值）
原理
我们考虑使用权值线段树，对原序列一个一个插入可持久化线段树。这样，线段树对应区间就是前若干数中该区间内数的个数。对于查询，我们考虑第r和第l-1棵线段树，对应区间值的差就是询问区间中的答案。所以我们的查询操作可以同时沿着这两棵线段树走。
实现
以下是查询操作的实现。
inline int query(int o1, int o2, int l, int r, int k) {
if(l == r) return l;
int mid = (l + r) >> 1;
int num = tree[tree[o2].lch].val - tree[tree[o1].lch].val;
if(k <= num) return query(tree[o1].lch, tree[o2].lch, l, mid, k);
else return query(tree[o1].rch, tree[o2].rch, mid + 1, r, k - num);
}
代码
本代码可以通过【P3834】【模板】可持久化线段树 1（主席树） – 洛谷一题。
// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while (c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 200005;
struct Node {
int lch, rch, val;
} tree[MAXN << 5];
int tot = 0, rt[MAXN];
inline void insert(int &o, int l, int r, int x) {
tree[++tot] = tree[o];
o = tot;
tree[o].val++;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) insert(tree[o].lch, l, mid, x);
else insert(tree[o].rch, mid + 1, r, x);
}
inline int query(int o1, int o2, int l, int r, int k) {
if(l == r) return l;
int mid = (l + r) >> 1;
int num = tree[tree[o2].lch].val - tree[tree[o1].lch].val;
if(k <= num) return query(tree[o1].lch, tree[o2].lch, l, mid, k);
else return query(tree[o1].rch, tree[o2].rch, mid + 1, r, k - num);
}
int n, m, a[MAXN], tmp[MAXN],ttot, l, r, k;
int main() {
n = readint();
m = readint();
for(int i = 1; i <= n; i++) {
a[i] = tmp[i] = readint();
}
std::sort(tmp + 1, tmp + n + 1);
ttot = std::unique(tmp + 1, tmp + n + 1) - tmp - 1;
for(int i = 1; i <= n; i++) {
rt[i] = rt[i - 1];
insert(rt[i], 1, ttot, std::lower_bound(tmp + 1, tmp + ttot + 1, a[i]) - tmp);
}
while(m--) {
l = readint();
r = readint();
k = readint();
printf("%d\n", tmp[query(rt[l - 1], rt[r], 1, ttot, k)]);
}
return 0;
}
![[BZOJ3938]Robot 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180225b-1-441x400.png)
![[JSOI2008]Blue Mary开公司 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180225a-346x400.png)
![[THUT2012]序列操作 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180223b.png)
[THUT2012]序列操作 题解
题目地址：洛谷：【P4247】[清华集训]序列操作 – 洛谷、BZOJ：Problem 2962. — 序列操作
题目描述
有一个长度为n的序列，有三个操作：
I a b c表示将[a, b]这一段区间的元素集体增加c；R a b表示将[a, b]区间内所有元素变成相反数；Q a b c表示询问[a, b]这一段区间中选择c个数相乘的所有方案的和mod 19940417的值。
输入输出格式
输入格式：
第一行两个数n, q表示序列长度和操作个数。
第二行n个非负整数，表示序列。
接下来q行每行输入一个操作I a b c或者R a b或者Q a b c，意义如题目描述。
输出格式：
对于每个询问，输出选出c个数相乘的所有方案的和mod 19940417的值。
输入输出样例
输入样例#1：
5 5 1 2 3 4 5 I 2 3 1 Q 2 4 2 R 1 5 I 1 3 -1 Q 1 5 1
输出样例#1：
40 19940397
说明
样例说明：
做完第一个操作序列变为1 3 4 4 5。
第一次询问结果为3 \times 4+3 \times 4+4 \times 4=40。
做完R操作变成-1 -3 -4 -4 -5。
做完I操作变为-2 -4 -5 -4 -5。
第二次询问结果为-2-4-5-4-5=-20。
数据范围：
对于100%的数据，n≤50000，q≤50000，初始序列的元素的绝对值≤109，保证[a, b]是一个合法区间，I操作中∣c∣≤109，Q操作中1≤c≤min(b−a+1, 20)。
题解
这个题里面有两种标记（相反数、区间加）和一种询问。我们分开来看。
标记与标记的应用
这里我们规定相反数的标记比加法标记优先级更高。试想，如果应用的顺序相反，可能会造成-a_i+add_i变成-(a_i+add_i)。
首先考虑区间信息的设置。应该记下本区间长度和一个f[21]数组，代表这个区间内对于每个c询问的答案。规定任意的f[0]为0。
如果要应用一个取相反数标记，应该将上述c为奇数时的情况的f值取相反数，因为偶数次相乘负号会抵消。
如果要应用一个区间加标记，思考对答案的改变，以f[15]这个值为例：
假如选择前15个值相乘，变化如下
[a_1, a_2, \cdots, a_{15}] \to [a_1 + c, a_2 + c, \cdots, a_{15} + c]
乘起来是这样的
f_{15} = C_{len-15}^0 \cdot c^0 \cdot f_{15} + C_{len-14}^1 \cdot c^1 \cdot f_{14} + C_{len-13}^2 \cdot c^2 \cdot f_{13} + \cdots + C_{len-0}^{15} \cdot c^{15} \cdot f_0
那我们就明白了，倒序求f值就好了。这里的C可以开始的时候预处理打个大表，空间是够的。区间加标记应用对应的代码长这样
inline void add(Data &dat, LL x) {
for(int i = std::min(dat.len, 20ll); i >= 0; i--) {
LL t = x;
for(int j = i - 1; j >= 0; j--) {
dat.f[i] = (dat.f[i] + dat.f[j] * C[dat.len - j][i - j] % MO * t % MO) % MO;
dat.f[i] = (dat.f[i] + MO) % MO;
t = t * x % MO;
}
}
dat.toadd = (dat.toadd + x) % MO;
}
区间合并
重点是要计算f值。首先考虑大区间选若干个是可以拆成左边选若干个和右边选若干个乘在一起的，这样既然左右两边的答案都是一堆乘积加起来，两块直接乘在一起就相当于两两配对后加起来，因此我们合并的公式就是：
f_k = \sum_{i=0}^k fl_i \times fr_{k-i}
上面式子的fl是左儿子f值，fr是右儿子f值。两层循环加一下就好。
代码
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while (c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 50005, MO = 19940417;
LL n, q, a, b, c, C[MAXN][21], val[MAXN];
char op;
inline bool isop(char c) {
return c == 'I' || c == 'R' || c == 'Q';
}
inline char readop() {
char c = fgc();
while (!isop(c)) c = fgc();
return c;
}
inline void calc() {
C[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= std::min(i, 20); j++) {
C[i][j] += C[i - 1][j];
if(j - 1 >= 0) C[i][j] += C[i - 1][j - 1];
C[i][j] %= MO;
}
}
}
#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)
struct Data {
LL len, toadd, f[21];
bool torev;
} tree[MAXN << 2];
inline void merge(Data &rt, Data ls, Data rs) {
rt.len = ls.len + rs.len;
memset(rt.f, 0, sizeof(rt.f));
for(int i = 0; i <= std::min(ls.len, 20ll); i++) {
for(int j = 0; j <= std::min(rs.len, 20ll); j++) {
if(i + j <= 20) rt.f[i + j] = (rt.f[i + j] + ls.f[i] * rs.f[j] % MO) % MO;
}
}
}
inline void build(int o, int l, int r) {
if(l == r) {
tree[o].len = 1;
tree[o].f[0] = 1;
tree[o].f[1] = val[l];
return;
}
build(lch, l, mid);
build(rch, mid + 1, r);
merge(tree[o], tree[lch], tree[rch]);
}
inline void add(Data &dat, LL x) {
for(int i = std::min(dat.len, 20ll); i >= 0; i--) {
LL t = x;
for(int j = i - 1; j >= 0; j--) {
dat.f[i] = (dat.f[i] + dat.f[j] * C[dat.len - j][i - j] % MO * t % MO) % MO;
dat.f[i] = (dat.f[i] + MO) % MO;
t = t * x % MO;
}
}
dat.toadd = (dat.toadd + x) % MO;
}
inline void rev(Data &dat) {
for(int i = 0; i <= std::min(dat.len, 20ll); i++) {
if(i & 1) {
dat.f[i] = (-dat.f[i] % MO + MO) % MO;
}
}
dat.torev = !dat.torev;
dat.toadd = (-dat.toadd % MO + MO) % MO;
}
inline void pushdown(int o) {
if(tree[o].torev) {
rev(tree[lch]);
rev(tree[rch]);
tree[o].torev = false;
}
if(tree[o].toadd != 0) {
add(tree[lch], tree[o].toadd);
add(tree[rch], tree[o].toadd);
tree[o].toadd = 0;
}
}
inline void modifyI(int o, int l, int r, int ll, int rr, LL v) {
if(l == ll && r == rr) {
add(tree[o], v);
return;
}
pushdown(o);
if(rr <= mid) {
modifyI(lch, l, mid, ll, rr, v);
} else if(ll > mid) {
modifyI(rch, mid + 1, r, ll, rr, v);
} else {
modifyI(lch, l, mid, ll, mid, v);
modifyI(rch, mid + 1, r, mid + 1, rr, v);
}
merge(tree[o], tree[lch], tree[rch]);
}
inline void modifyR(int o, int l, int r, int ll, int rr) {
if(l == ll && r == rr) {
rev(tree[o]);
return;
}
pushdown(o);
if(rr <= mid) {
modifyR(lch, l, mid, ll, rr);
} else if(ll > mid) {
modifyR(rch, mid + 1, r, ll, rr);
} else {
modifyR(lch, l, mid, ll, mid);
modifyR(rch, mid + 1, r, mid + 1, rr);
}
merge(tree[o], tree[lch], tree[rch]);
}
inline Data query(int o, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) {
return tree[o];
}
pushdown(o);
if(rr <= mid) {
return query(lch, l, mid, ll, rr);
} else if(ll > mid) {
return query(rch, mid + 1, r, ll, rr);
} else {
Data res;
merge(res, query(lch, l, mid, ll, mid), query(rch, mid + 1, r, mid + 1, rr));
return res;
}
}
int main() {
n = readint();
q = readint();
calc();
for(int i = 1; i <= n; i++) {
val[i] = readint();
val[i] = (val[i] % MO + MO) % MO;
}
build(1, 1, n);
while(q--) {
op = readop();
if(op == 'I') {
a = readint();
b = readint();
c = readint();
c = (c % MO + MO) % MO;
modifyI(1, 1, n, a, b, c);
}
if(op == 'R') {
a = readint();
b = readint();
modifyR(1, 1, n, a, b);
}
if(op == 'Q') {
a = readint();
b = readint();
c = readint();
Data res = query(1, 1, n, a, b);
printf("%lld\n", res.f[c]);
}
}
return 0;
}
![[SHOI2008]堵塞的交通 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180223a-541x400.png)
![[JSOI2009]等差数列 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180221a-432x400.png)
![[SCOI2011]棘手的操作 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180212a.png)
[SCOI2011]棘手的操作 题解
题目地址：洛谷：【P3273】[SCOI2011]棘手的操作 – 洛谷、BZOJ：Problem 2333. — [SCOI2011]棘手的操作
题目描述
有N个节点，标号从1到N，这N个节点一开始相互不连通。第i个节点的初始权值为a[i]，接下来有如下一些操作：
U x y: 加一条边，连接第x个节点和第y个节点A1 x v: 将第x个节点的权值增加vA2 x v: 将第x个节点所在的连通块的所有节点的权值都增加vA3 v: 将所有节点的权值都增加vF1 x: 输出第x个节点当前的权值F2 x: 输出第x个节点所在的连通块中，权值最大的节点的权值F3: 输出所有节点中，权值最大的节点的权值
输入输出格式
输入格式：
输入的第一行是一个整数N，代表节点个数。接下来一行输入N个整数，a[1], a[2], …, a[N]，代表N个节点的初始权值。再下一行输入一个整数Q，代表接下来的操作数。最后输入Q行，每行的格式如题目描述所示。
输出格式：
对于操作F1, F2, F3，输出对应的结果，每个结果占一行。
输入输出样例
输入样例#1：
3 0 0 0 8 A1 3 -20 A1 2 20 U 1 3 A2 1 10 F1 3 F2 3 A3 -10 F3
输出样例#1：
-10 10 10
说明
对于30%的数据，保证 N<=100，Q<=10000
对于80%的数据，保证 N<=100000，Q<=100000
对于100%的数据，保证 N<=300000，Q<=300000
对于所有的数据，保证输入合法，并且 -1000<=v, a[1], a[2], …, a[N]<=1000
题解
解法1：线段树 + 并查集
考虑离线解决这个题，我们可以把操作中同一连通块的元素连续地排列在一个序列中，这样连通块操作就变成了区间操作，这个可以用线段树维护区间最大值。
至于如何连续排列，可以考虑用链表来存储当前连通块序列，然后合并连通块的时候合并链表，这样就自然成为连续的一段了。最后再遍历链表给节点加编号就好。
解法2：可并堆
使用可并堆做这个题目就很裸了，也不需要离线。这里我写的是左偏树。
分开管理两类可并堆，一类是联通块的大根堆，一类是所有联通块堆顶元素的大根堆（换句话说，这是一个维护全局的堆）。
U操作：将两个节点所在的堆合并，删去全局堆中消失的那个堆的对顶。
A1操作：将x所在堆中x元素删去，更新x元素的值，再插回去。
A2操作：将x所在堆全局增量加上v。堆全局增量可以在堆顶维护，需要统计这个结点的真实值的时候从该点一路上跳，跳到一个父亲就将该父亲的增量加入真实值。（因为堆并过程中增量仍然在被合并的堆顶）
A3操作：维护总全局增量加v。
F1操作：查询x的真实值。
F2操作：查询x所在堆堆顶的真实值。
F3操作：查询全局堆堆顶的真实值。
这个解法的代码我借鉴了远航之曲的实现思路。
代码
解法1
// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>
struct io {
char buf[1 << 26], *op;
io() {
fread(op = buf, 1, 1 << 26, stdin);
}
inline int readint() {
register int res = 0, neg = 1;
while(*op < '0' || *op > '9') if(*op++ == '-') neg = -1;
while(*op >= '0' && *op <= '9') res = res * 10 + *op++ - '0';
return res * neg;
}
inline char readchar() {
return *op++;
}
} ip;
#define readint ip.readint
#define readchar ip.readchar
inline bool isop(char c) {
return c == 'A' || c == 'U' || c == 'F';
}
inline char readop() {
char c;
while(!isop(c = readchar()));
return c;
}
int n, a[300005], q, opop1[300005], opx[300005], opy[300005], idx[300005], inv[300005], tot = 1;
char opop[300005];
// Linked List
int pre[300005], nxt[300005], head[300005], tail[300005];
// Union-Find
int fa[300005];
inline int find(int x) {
int r = x;
while(fa[r] != r) r = fa[r];
while(fa[x] != x) {
int ofa = fa[x];
fa[x] = r;
x = ofa;
}
return r;
}
// Seg Tree
#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)
int tree[1200005], lazy[1200005];
inline void build(int o, int l, int r) {
if(l == r) {
tree[o] = a[inv[l]];
return;
}
build(lch, l, mid);
build(rch, mid + 1, r);
tree[o] = std::max(tree[lch], tree[rch]);
}
inline void pushdown(int o) {
if(lazy[o] != 0) {
lazy[lch] += lazy[o];
lazy[rch] += lazy[o];
tree[lch] += lazy[o];
tree[rch] += lazy[o];
lazy[o] = 0;
}
}
inline void add(int o, int l, int r, int ll, int rr, int v) {
if(l == ll && r == rr) {
tree[o] += v;
lazy[o] += v;
return;
}
pushdown(o);
if(rr <= mid) {
add(lch, l, mid, ll, rr, v);
} else if(ll > mid) {
add(rch, mid + 1, r, ll, rr, v);
} else {
add(lch, l, mid, ll, mid, v);
add(rch, mid + 1, r, mid + 1, rr, v);
}
tree[o] = std::max(tree[lch], tree[rch]);
}
inline int query(int o, int l, int r, int ll, int rr) {
if(l == ll && r == rr) {
return tree[o];
}
pushdown(o);
if(rr <= mid) {
return query(lch, l, mid, ll, rr);
} else if(ll > mid) {
return query(rch, mid + 1, r, ll, rr);
} else {
return std::max(query(lch, l, mid, ll, mid), query(rch, mid + 1, r, mid + 1, rr));
}
}
int main() {
n = readint();
for(int i = 1; i <= n; i++) {
a[i] = readint();
fa[i] = head[i] = tail[i] = i;
}
q = readint();
for(int i = 1; i <= q; i++) {
opop[i] = readop();
if(opop[i] == 'U') {
opx[i] = readint();
opy[i] = readint();
int f1 = find(opx[i]), f2 = find(opy[i]);
if(f1 != f2) {
fa[f2] = f1;
pre[head[f2]] = tail[f1];
nxt[tail[f1]] = head[f2];
tail[f1] = tail[f2];
}
} else if(opop[i] == 'A') {
opop1[i] = readint();
if(opop1[i] < 3) {
opx[i] = readint();
}
opy[i] = readint();
} else if(opop[i] == 'F') {
opop1[i] = readint();
if(opop1[i] < 3) {
opx[i] = readint();
}
}
}
for(int i = 1; i <= n; i++) {
if(!pre[i]) {
for(int j = i; j; j = nxt[j]) {
idx[j] = tot++;
inv[idx[j]] = j;
}
}
}
build(1, 1, n);
for(int i = 1; i <= n; i++) {
fa[i] = head[i] = tail[i] = i;
}
for(int i = 1; i <= q; i++) {
if(opop[i] == 'U') {
int f1 = find(idx[opx[i]]), f2 = find(idx[opy[i]]);
if(f1 != f2) {
fa[f2] = f1;
if(head[f1] < head[f2]) {
tail[f1] = tail[f2];
} else {
head[f1] = head[f2];
}
}
} else if(opop[i] == 'A') {
if(opop1[i] == 1) {
add(1, 1, n, idx[opx[i]], idx[opx[i]], opy[i]);
} else if(opop1[i] == 2) {
int f = find(idx[opx[i]]);
add(1, 1, n, head[f], tail[f], opy[i]);
} else {
add(1, 1, n, 1, n, opy[i]);
}
} else if(opop[i] == 'F') {
if(opop1[i] == 1) {
printf("%d\n", query(1, 1, n, idx[opx[i]], idx[opx[i]]));
} else if(opop1[i] == 2) {
int f = find(idx[opx[i]]);
printf("%d\n", query(1, 1, n, head[f], tail[f]));
} else {
printf("%d\n", query(1, 1, n, 1, n));
}
}
}
return 0;
}
解法2
// Code by KSkun, 2018/2
#include <cstdio>
#include <queue>
struct io {
char buf[1 << 26], *op;
io() {
fread(op = buf, 1, 1 << 26, stdin);
}
inline int readint() {
register int res = 0, neg = 1;
while(*op < '0' || *op > '9') if(*op++ == '-') neg = -1;
while(*op >= '0' && *op <= '9') res = res * 10 + *op++ - '0';
return res * neg;
}
inline char readchar() {
return *op++;
}
} ip;
#define readint ip.readint
#define readchar ip.readchar
inline bool isop(char c) {
return c == 'U' || c == 'A' || c == 'F';
}
inline void readop(char* str) {
char c;
while(!isop(c = readchar()));
str[0] = c;
if(c == 'A' || c == 'F') str[1] = readchar();
}
int n, m, x, y, z, add = 0;
char op[5];
struct LeftistTree {
int dis[300005], fa[300005], ch[300005][2], val[300005], add[300005], root;
inline int toadd(int x) {
int res = 0;
while(x = fa[x]) res += add[x];
return res;
}
inline void clear(int x) {
fa[x] = ch[x][0] = ch[x][1] = 0;
}
inline void pushdown(int x) {
if(ch[x][0]) {
val[ch[x][0]] += add[x];
add[ch[x][0]] += add[x];
}
if(ch[x][1]) {
val[ch[x][1]] += add[x];
add[ch[x][1]] += add[x];
}
add[x] = 0;
}
inline int merge(int x, int y) {
if(!x) return y;
if(!y) return x;
if(val[x] < val[y]) std::swap(x, y);
pushdown(x);
ch[x][1] = merge(ch[x][1], y);
fa[ch[x][1]] = x;
if(dis[ch[x][0]] < dis[ch[x][1]]) std::swap(ch[x][0], ch[x][1]);
dis[x] = dis[ch[x][1]] + 1;
return x;
}
inline int froot(int x) {
while(fa[x]) x = fa[x];
return x;
}
inline void delet(int x) {
pushdown(x);
int f = merge(ch[x][0], ch[x][1]);
fa[f] = fa[x];
if(fa[x]) ch[fa[x]][ch[fa[x]][0] == x ? 0 : 1] = f;
int t = fa[x];
if(!t) {
root = f;
return;
}
while(t) {
if(dis[ch[t][0]] < dis[ch[t][1]]) std::swap(ch[t][0], ch[t][1]);
if(dis[t] == dis[ch[t][1]] + 1) return;
dis[t] = dis[ch[t][1]] + 1;
if(!fa[t]) root = t;
t = fa[t];
}
}
inline void addtree(int x, int v) {
int rt = froot(x);
val[rt] += v;
add[rt] += v;
}
inline int addpoint(int x, int v) {
int rt = froot(x);
if(rt == x) {
if(!ch[x][0] && !ch[x][1]) {
val[x] += v;
return x;
} else {
rt = ch[x][0] ? ch[x][0] : ch[x][1];
}
}
delet(x);
val[x] += v + toadd(x);
clear(x);
return merge(froot(rt), x);
}
inline void build() {
std::queue<int> que;
for(int i = 1; i <= n; i++) {
que.push(i);
}
while(que.size() > 1) {
int x = que.front();
que.pop();
int y = que.front();
que.pop();
que.push(merge(x, y));
}
root = que.front();
}
};
LeftistTree lt1, lt2;
int main() {
n = readint();
for(int i = 1; i <= n; i++) {
lt1.val[i] = lt2.val[i] = readint();
}
lt1.dis[0] = lt2.dis[0] = -1;
lt2.build();
m = readint();
for(int i = 1; i <= m; i++) {
readop(op);
if(op[0] == 'U') {
x = readint();
y = readint();
int fx = lt1.froot(x), fy = lt1.froot(y), rt;
if(fx != fy) {
rt = lt1.merge(fx, fy);
if(rt == fx) lt2.delet(fy);
if(rt == fy) lt2.delet(fx);
}
}
if(op[0] == 'A') {
if(op[1] == '1') {
x = readint();
y = readint();
int fx = lt1.froot(x), rt;
lt2.delet(fx);
rt = lt1.addpoint(x, y);
lt2.val[rt] = lt1.val[rt];
lt2.clear(rt);
lt2.root = lt2.merge(lt2.root, rt);
}
if(op[1] == '2') {
x = readint();
y = readint();
int fx = lt1.froot(x);
lt2.delet(fx);
lt1.val[fx] += y;
lt1.add[fx] += y;
lt2.val[fx] = lt1.val[fx];
lt2.clear(fx);
lt2.root = lt2.merge(lt2.root, fx);
}
if(op[1] == '3') {
x = readint();
add += x;
}
}
if(op[0] == 'F') {
if(op[1] == '1') {
x = readint();
printf("%d\n", lt1.val[x] + lt1.toadd(x) + add);
}
if(op[1] == '2') {
x = readint();
printf("%d\n", lt1.val[lt1.froot(x)] + add);
}
if(op[1] == '3') {
printf("%d\n", lt2.val[lt2.root] + add);
}
}
}
return 0;
}
调试留下来的数据生成器
因为经常WA，手写了一个数据生成器，偶尔会崩掉不要介意qwq，可自由调整n和q的取值。
// Code by KSkun, 2018/2
#include <cstdio>
#include <cstdlib>
#include <ctime>
int n, q;
char str[10][5] = {"U", "A1", "A2", "A3", "F1", "F2", "F3"};
int main() {
freopen("p3273.in", "w", stdout);
srand(time(NULL));
n = rand() % 50;
q = rand() % 50;
printf("%d\n", n);
for(int i = 1; i <= n; i++) {
printf("%d ", rand() - RAND_MAX / 2);
}
printf("\n");
printf("%d\n", q);
for(int i = 1; i <= q; i++) {
int op = rand() % 7;
printf("%s ", str[op]);
if(op == 0) {
printf("%d %d ", rand() % n + 1, rand() % n + 1);
}
if(op == 1 || op == 2 || op == 4 || op == 5) {
printf("%d ", rand() % n + 1);
}
if(op == 1 || op == 2 || op == 3) {
printf("%d ", rand() - RAND_MAX / 2);
}
printf("\n");
}
return 0;
}
![[IOI1998]Picture 题解](https://ksmeow.moe/wp-content/uploads/2018/02/180210a-760x400.png)
