很早就有人给我推荐的模版题，然后我最近才刷的(' ' ) 昨天的tree 不知道比他们高到哪里去了，我和他谈笑风生啊！
bzoj 2002 弹飞绵羊
重点：这道题的cut和link 由于这道题链的特殊性所以不能用提根的方法搞，可以注意到每一次cut位置一定是前面的一个元素，所以access 上去之后直接把左边的儿子丢掉就行了（我原来的cut 是在不知道两个点的儿子关系时就强行提根(' ' )） 然后link的时候直接把cut的那一棵splay接过去就行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ;
struct node {
int size, p, data;
node* son[], *fa;
}tr[maxn]; void test(node* x) {
if(x) {
cout << x-> data <<" " << x-> size <<" "<< x-> p << endl;
for(int i = ; i < ; ++ i) test(x-> son[i]);
}
}
void update(node* x) {
x-> size = ;
for(int i = ; i < ; ++ i) if(x-> son[i]) x-> size += x-> son[i]-> size;
} void rotate(node* x, int f) {
node* y = x-> fa;
if(y-> fa) {
if(y-> fa-> son[] == y) y-> fa-> son[] = x;
else y-> fa-> son[] = x;
}
x-> fa = y-> fa, y-> fa = x, x-> p = y-> p, x-> size = y-> size;
y-> son[f] = x-> son[!f];
if(x->son[!f]) x-> son[!f]-> fa = y;
x-> son[!f] = y;
update(y);
} void splay(node* x, node* f) {
while(x-> fa != f) {
if(x-> fa-> fa == f) {
int a = x-> fa-> son[] == x ? : ;
rotate(x, a);
}
else {
node* y = x-> fa, *z = y-> fa;
int a = z-> son[] == y ? : ;
int b = y-> son[] == x ? : ;
if(a == b) rotate(y, a), rotate(x, b);
else rotate(x, b), rotate(x, a);
}
}
} void access(int cur) {
node* x = tr + cur; node* y; int pp;
splay(x, NULL);
if(x-> son[]) x-> son[]-> p = cur, x-> son[]-> fa = NULL, x-> son[] = NULL, update(x);
while((pp = x-> p)) {
y = tr + pp; splay(y, NULL);
if(y-> son[]) y-> son[]-> p = pp, y-> son[]-> fa = NULL, y-> son[] = NULL, update(y);
y-> son[] = x, x-> fa = y; update(y);
splay(x, NULL);
}
} int int_get() {
int x = ; char c = (char)getchar(); bool f = ;
while(!isdigit(c) && c != '-') c = (char)getchar();
if(c == '-') f = , c = (char)getchar();
while(isdigit(c)) {
x = x * + (int)(c - '');
c = (char)getchar();
}
if(f) x = -x;
return x;
} int n, m, px[maxn]; void read() {
n = int_get();
for(int i = ; i <= n; ++ i) {
int ne = int_get();
px[i] = ne + i > n ? : i + ne;
(tr + i)-> size = , (tr + i)-> p = px[i], (tr + i)-> data = i;
}
} void sov() {
int m = int_get();
while(m --) {
int op = int_get();
if(op == ) {
int x = int_get() + ; access(x); printf("%d\n", (tr + x)-> size);
}
else {
int a, b;
a = int_get() + , b = int_get();
access(a); node* x = tr + a;
if(px[a]) x-> son[]-> p = , x-> son[]-> fa = NULL, x-> son[] = NULL; update(x);
px[a] = a + b > n ? : a + b;
x-> p = px[a];
}
}
} int main() {
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
read();
sov();
return ;
}
bzoj 2049 洞穴勘探
非常裸的操作，不过我查询是在splay上暴力，应该有更好的方法(' ' )
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ; struct node {
int size, p, lr, data;
node *son[], *fa;
}tr[maxn]; void test(node* x) {
if(x) {
cout << x-> data <<" "<< x-> size <<" "<< x-> p <<" "<< x-> lr << endl;
for(int i = ; i < ; ++ i) test(x-> son[i]);
}
} void update(node* x) {
x-> size = ;
for(int i = ; i < ; ++ i) if(x-> son[i]) x-> size += x-> son[i]-> size;
} void swap(node* &a, node* &b) {
node* mid = a; a = b, b = mid;
} void pushdown(node* x) {
if(x && x-> lr) {
swap(x-> son[], x-> son[]);
for(int i = ; i < ; ++ i) if(x-> son[i]) x-> son[i]-> lr ^= ;
x-> lr = ;
}
} void rotate(node* x, int f) {
node* y = x-> fa;
if(y-> fa) {
if(y-> fa-> son[] == y) y-> fa-> son[] = x;
else y-> fa-> son[] = x;
}
x-> fa = y-> fa, y-> fa = x, x-> size = y-> size, x-> p = y-> p;
y-> son[f] = x-> son[!f];
if(x-> son[!f]) x-> son[!f]-> fa = y;
x-> son[!f] = y;
update(y);
} void splay(node* x, node* f) {
pushdown(x);
while(x-> fa != f) {
pushdown(x-> fa-> fa), pushdown(x-> fa), pushdown(x);
if(x-> fa-> fa == f) {
int a = x-> fa-> son[] == x ? : ;
rotate(x, a);
}
else {
node* y = x-> fa, *z = y-> fa;
int a = z-> son[] == y ? : ;
int b = y-> son[] == x ? : ;
if(a == b) rotate(y, a), rotate(x, b);
else rotate(x, b), rotate(x, a);
}
}
} void access(int cur) {
node* x = tr + cur, *y; int pp;
splay(x, NULL); if(x-> son[]) x-> son[]-> fa = NULL, x-> son[]-> p = cur, x-> son[] = NULL, update(x);
while((pp = x-> p)) {
y = tr + pp; splay(y, NULL);
if(y-> son[]) y-> son[]-> fa = NULL, y-> son[]-> p = pp, y-> son[] = NULL, update(y);
y-> son[] = x, x-> fa = y; update(y);
splay(x, NULL);
}
} void reserve(int cur) {
access(cur);
(tr + cur)-> lr ^= ;
} void cut(int a, int b) {
reserve(a), access(b);
(tr + a)-> p = , (tr + a)-> fa = NULL, (tr + b)-> son[] = NULL;
update(tr + a), update(tr + b);
} void link(int a, int b) {
reserve(a), access(b);
(tr + a)-> p = b;
update(a + tr), update(b + tr);
} bool query(int a, int b) {
reserve(a); access(b);
node* x = tr + a;
while(x-> fa) x = x-> fa;
return x == (tr + b);
} int int_get() {
int x = ; char c = (char)getchar(); bool f = ;
while(!isdigit(c) && c != '-' ) c = (char)getchar();
if(c == '-') c = (char)getchar(), f = ;
while(isdigit(c)) {
x = x * + (int)(c - '');
c = (char)getchar();
}
if(f) x = -x;
return x;
} int n, m; void sov() {
n = int_get(), m = int_get();
for(int i = ; i <= n; ++ i) (tr + i)-> size = , (tr + i)-> p = (tr + i)-> lr = , (tr + i)-> data = i;
while(m --) {
char s[]; scanf("%s", s + );
int a, b; a = int_get(), b = int_get();
if(s[] == 'C') link(a, b);
if(s[] == 'D') cut(a, b);
if(s[] == 'Q') {
if(query(a, b)) printf("Yes\n");
else printf("No\n");
}
}
} int main() {
//freopen("test.in", "r", stdin);
sov();
// test(tr + 123);
}