# 不是很懂为什么这份代码不开O2 AC开了就全RE

@ZCDHJ 2018-12-02 21:44 回复

RT，求助 线段树合并

#include <iostream>
#include <cstdio>

const int MAXN = 1e5;

int n, m;
int fset[MAXN | 1], a[MAXN | 1];

register int x = 0;
register char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}

namespace Segtree {
struct Segtree {
int sumv;
Segtree *ch[2];
Segtree(Segtree *ch0 = NULL, Segtree *ch1 = NULL, int _sumv = 0) : sumv(_sumv) {
ch[0] = ch0;
ch[1] = ch1;
}
} *root[MAXN | 1];
inline int sumv(Segtree *o) { return o == NULL ? 0 : o -> sumv; }
void insert(Segtree *&o, int pos, int l = 1, int r = n) {
if(o == NULL) o = new Segtree;
++(o -> sumv);
if(l == r) return;
int mid = (l + r) >> 1;
pos <= mid ? insert(o -> ch[0], pos, l, mid) : insert(o -> ch[1], pos, mid + 1, r);
}
int kth(Segtree *o, int k, int l = 1, int r = n) {
if(k > sumv(o)) return -1;
if(l == r) return l;
int mid = (l + r) >> 1;
if(sumv(o -> ch[0]) >= k) return kth(o -> ch[0], k, l, mid);
else return kth(o -> ch[1], k - sumv(o -> ch[0]), mid + 1, r);
}
Segtree *merge(Segtree *x, Segtree *y, int l = 1, int r = n) {
if(x == NULL) return y;
if(y == NULL) return x;
if(l == r) return new Segtree(NULL, NULL, x -> sumv + y -> sumv);
int mid = (l + r) >> 1;
return new Segtree(merge(x -> ch[0], y -> ch[0], l, mid), merge(x -> ch[1], y -> ch[1], mid + 1, r), x -> sumv + y -> sumv);
}
}

int find(int x) { return fset[x] == x ? x : fset[x] = find(fset[x]); }

inline void merge(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return;
fset[y] = x;
Segtree::root[x] = Segtree::merge(Segtree::root[x], Segtree::root[y]);
}

inline int query(int x, int y) {
x = find(x);
int res = Segtree::kth(Segtree::root[x], y);
return res == -1 ? -1 : a[res];
}

int main() {
for(int i = 1; i <= n; ++i) {
a[tmp] = i;
Segtree::insert(Segtree::root[i], tmp);
fset[i] = i;
}
for(int q = read(); q >= 1; --q) {
char ch = getchar();
while(ch < 'A' || ch > 'Z') ch = getchar();
}