[hnoi2010] flying sheep

Sequence tree building

link ：[P3203 HNOI2010] Flying sheep - Luogu | New ecology of computer science education (luogu.com.cn)

The question ： Given sequence a , from 0 Start to n-1, Each time from i The departure can be adjusted to i+a[i] , Repeated inquiries and modifications , Ask how many times you can jump to greater than or equal to n The location of , The revision will a[x] Change to y .
Answer key ： Use the whole sequence LCT Build up trees , Move all positions one position back , The root node is n+1 . You can add edges every time you modify the broken edges . Remember to put... First when asking n+1 Reset to the root node with the smallest depth , Because the root has changed when connecting edges or short edges . And then x Put it in splay The root of the （ Not the smallest depth ）, Finding the size of the left subtree is the answer , Represents how many x To the parent node of the root .

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
const int maxn=2e5+5;

int a[maxn],n,m,op,x,y,z;
int f[maxn],c[maxn][2],sz[maxn],st[maxn];
bool r[maxn];
#define lc c[x][0]
#define rc c[x][1]

bool nroot(int x)
{
    
	return c[f[x]][0]==x||c[f[x]][1]==x;
}

void pushup(int x)
{
    
	sz[x]=sz[lc]+sz[rc]+1;
}

void reverse(int x)
{
    
	swap(lc,rc); r[x]^=1;
}

void pushdown(int x)
{
    
	if(r[x])
	{
    
		if(lc)reverse(lc);
		if(rc)reverse(rc);
		r[x]=0;
	}
}

void rotate(int x)
{
    
	int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
	if(nroot(y))c[z][c[z][1]==y]=x; 
	c[x][!k]=y,c[y][k]=w;
	if(w)f[w]=y; f[y]=x,f[x]=z;
	pushup(y);
}

void splay(int x)
{
    
	int y=x,z=0;
	st[++z]=y;
	while(nroot(y))st[++z]=y=f[y];
	while(z)pushdown(st[z--]);
	while(nroot(x))
	{
    
		y=f[x],z=f[y];
		if(nroot(y))
		{
    
			rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
		}
		rotate(x);
	}
	pushup(x);
}

void access(int x)
{
    
	for(int y=0;x;x=f[y=x])
	{
    
		splay(x),rc=y,pushup(x);
	}
}

void makeroot(int x)
{
    
	access(x),splay(x),reverse(x);
}

int findroot(int x)
{
    
	access(x),splay(x);
	while(lc)pushdown(x),x=lc;
	splay(x); return x;
}

void split(int x,int y)
{
    
	makeroot(x),access(y),splay(y);
}

void link(int x,int y)
{
    
	makeroot(x),f[x]=y;
}

void cut(int x,int y)
{
    
	split(x,y),f[x]=c[y][0]=0;
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
    
		cin>>a[i]; 
		if(i+a[i]<=n)link(i,i+a[i]);
		else link(i,n+1);
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
    
		cin>>op;
		if(op==1)
		{
    
			cin>>x; x++; makeroot(n+1),access(x),splay(x);
			cout<<sz[lc]<<"\n";
		}
		else
		{
    
			cin>>x>>y; x++;
			if(x+a[x]<=n)cut(x,x+a[x]);
			else cut(x,n+1);
			if(x+y<=n)link(x,x+y);
			else link(x,n+1);
			a[x]=y;
		}
	}
	return 0;
}