上一次用分块过了, 今天换了一种lct(link-cut tree)的写法。
学lct之前要先学过splay。
lct 简单的来说就是 一颗树, 然后每次起作用的都是其中的某一条链。
所以每次如果需要用到一条链, 就要先 access 一下某个位置, 到root, 将其他的非法的东西抠掉。
并且 一个很大的特点就是 假设现在有u,v2个节点, 存在一条边 u -> v, 那么 u 的 父亲指向 v 但是 v 不一定存在 儿子节点指向 u , 也就是说很多时候是单向边。
然后对于整个lct来说, 他由很多个splay组成的。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch tr[x].son[0]
#define rch tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
int n, t;
struct Node{
int son[], pre;
int sz, is_root;
inline void init() {
son[] = son[] = pre = ;
sz = is_root =;
}
}tr[N];
void Push_Up(int x){
if(!x) return ;
tr[x].sz = tr[lch].sz + tr[rch].sz + ;
}
void rotate(int x){
if(tr[x].is_root) return ;
int y = tr[x].pre, z = tr[y].pre;
int k = x == tr[y].son[];
tr[y].son[k] = tr[x].son[k^];
tr[tr[y].son[k]].pre = y;
tr[x].son[k^] = y;
tr[y].pre = x;
tr[x].pre = z;
if(tr[y].is_root) tr[x].is_root = , tr[y].is_root = ;
else tr[z].son[ tr[z].son[] == y] = x;
Push_Up(y); }
void Splay(int x){
while(!tr[x].is_root){
int y = tr[x].pre, z = tr[y].pre;
if(!tr[y].is_root){
if((y == tr[z].son[]) != ( x == tr[y].son[])) rotate(y);
else rotate(x);
}
rotate(x);
}
Push_Up(x);
}
void access(int x){
int y = ;
do{
Splay(x);
tr[rch].is_root = ;
rch = y;
tr[rch].is_root = ;
Push_Up(x);
y = x;
x = tr[x].pre;
}while(x);
}
inline void link(int u, int v){
if(v > n) v = ;
tr[u].pre = v;
}
inline void cut(int x){
access(x);
Splay(x);
tr[lch].is_root = ;
tr[lch].pre = ;
lch = ;
Push_Up(x);
}
inline int Query(int x){
access(x);
Splay(x);
return tr[lch].sz + ;
}
int main(){
scanf("%d", &n);
for(int i = ; i <= n; i++) tr[i].init();
for(int i = ; i <= n; i++){
scanf("%d", &t);
link(i, t+i);
}
int m, op, x, k;
scanf("%d", &m);
while(m--){
scanf("%d", &op);
if(op == ) {
scanf("%d", &x);
printf("%d\n", Query(x+));
}
else {
scanf("%d%d", &x, &k);
cut(x+);
link(x+, x+k+);
}
}
return ;
}