20200726模拟赛 C.树高

待填。

人生第一次在$AC$前有90次提交记录的题。
人生第一次写了$10K$代码的题（写完$6KTreap$发现$TLE$的死死的然后开始写$7KSplay$然后卡了一个世纪。）

$\mathcal AC \ Code$

#include<bits/stdc++.h>
#define maxn 200005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define C 31
#define lim 17
#define il inline
using namespace std;

char Start;
namespace IO{
	char cb[1<<16] ,*cs=cb,*ct=cb;
	#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++)
	inline void read(int &res){
		char ch;bool f = 0;
		for(;!isdigit(ch=getc());) if(ch == '-') f = 1;
		for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
		(f) && (res = -res);
	}
	char wb[1 << 23] , *ws = wb;
	inline void print(int a,char c){
		static int q[20]={};
		if(a < 0) *ws ++ = '-' , a = -a;
		for(;a; a/= 10) q[++q[0]] = a % 10;
		if(!q[0]) *ws++ = '0';
		for(;q[0];) *ws++ = '0' + q[q[0] --];
		*ws ++ = c;
	}
	void flush(){
		fwrite(wb,1,ws-wb,stdout);
		ws = wb;
	}
}

using IO :: print;
using IO :: flush;
using IO :: read;

int n,f[lim][maxn];
int rt[maxn][C+1] , dep[maxn] , st[maxn] , ed[maxn];
int fa[maxn] , ch[maxn][2] , sz[maxn][C+1] , xsz[maxn][C+1] , col[maxn] , rot[maxn] , tgrt[maxn] , tgcl[maxn] , mx[maxn] , mn[maxn] , key[maxn];

int Gets(int u,int v){
	per(i,lim-1,0) if(dep[f[i][u]] > dep[v])
		u = f[i][u];
	return u;
}

il void dtrt(int u,int x){
	if(!u) return ;
	tgrt[u] = x , rot[u] = x;
}

il void dtcl(int u,int x){
	if(!u) return ;
	tgcl[u] = x , col[u] = x;
}

il void dt(int u){
	if(!u) return ;
	if(tgrt[u] != -1) dtrt(ch[u][0] , tgrt[u]) , dtrt(ch[u][1] , tgrt[u]) , tgrt[u] = -1;
	if(tgcl[u] != 0) dtcl(ch[u][0] , tgcl[u]) , dtcl(ch[u][1] , tgcl[u]) , tgcl[u] = 0;
}

il void upd(int u){
	if(!u) return ;
	int i=0 , l = ch[u][0] , r = ch[u][1] , *su = sz[u] , *sl = sz[l] , *sr = sz[r] , *xsu = xsz[u];
	for(;i+7<=C;i+=8) 
		su[i] = sl[i] + sr[i] + xsu[i],
		su[i+1] = sl[i+1] + sr[i+1] + xsu[i+1],
		su[i+2] = sl[i+2] + sr[i+2] + xsu[i+2],
		su[i+3] = sl[i+3] + sr[i+3] + xsu[i+3],
		su[i+4] = sl[i+4] + sr[i+4] + xsu[i+4],
		su[i+5] = sl[i+5] + sr[i+5] + xsu[i+5],
		su[i+6] = sl[i+6] + sr[i+6] + xsu[i+6],
		su[i+7] = sl[i+7] + sr[i+7] + xsu[i+7];
/*	su[i] = sl[i] + sr[i] + xsu[i],
	su[i+1] = sl[i+1] + sr[i+1] + xsu[i+1],
	su[i+2] = sl[i+2] + sr[i+2] + xsu[i+2],
	su[i+3] = sl[i+3] + sr[i+3] + xsu[i+3],
	su[i+4] = sl[i+4] + sr[i+4] + xsu[i+4],
	su[i+5] = sl[i+5] + sr[i+5] + xsu[i+5],
	su[i+6] = sl[i+6] + sr[i+6] + xsu[i+6];*/

	mx[u] = mn[u] = dep[(u+1) / 2] , 
	mx[u] = max(mx[u] , max(mx[l] , mx[r]));
	mn[u] = min(mn[u] , min(mn[l] , mn[r]));
}

il int inr(int u){ return ch[fa[u]][1] == u; }
il int isr(int u){ return fa[u] == 0; }

void rotate(int x){
	int y = fa[x] , z = fa[y] , c = inr(x);
	if(!isr(y)) ch[z][inr(y)] = x;
	(ch[y][c] = ch[x][!c]) && (fa[ch[y][c]] = y);
	fa[fa[ch[x][!c]=y]=x]=z;
	upd(y);
}

void dtpath(int u){
	if(fa[u]) dtpath(fa[u]);
	dt(u);
}

void splay(int u,int goal){
	if(!u) return;
	for(dtpath(u);fa[u] != goal;rotate(u))
		if(fa[fa[u]] != goal)
			rotate(inr(fa[u]) ^ inr(u) ? u : fa[u]);
	upd(u);
}

void merge(int &u,int l,int r){
	if(!l || !r) return (void)(u = l + r);
	splay(r,0);
	for(;ch[r][0];r = ch[r][0]);
	splay(r,0);
	splay(l,0);
	ch[r][0] = l , fa[l] = r;
	upd(r);
	u = r;
}

void split(int &u,int &l,int &r,int v){
	splay(v,0);
	r = ch[v][1];
	ch[v][1] = fa[ch[v][1]] = 0;
	l = v;
	upd(v);
}

void split(int &u,int &a,int &b,int &c,int A,int B){
	splay(A,0);
	a = ch[A][0];
	fa[a] = ch[A][0] = 0;
	upd(A);
	
	splay(B,0);
	c = ch[B][1];
	fa[c] = ch[B][1] = 0;
	upd(B);
	
	b = B;
}

int serk(int u,int pr = 0){
	int r = pr ? (ch[u][1] == pr) * (sz[ch[u][0]][0] + 1) : (sz[ch[u][0]][0] + 1);
	if(fa[u]) r += serk(fa[u],u);
	dt(u);
	return r;
}
il int sert(int u){
	for(;fa[u]; u = fa[u]);
	return u;
}

void ins(int u,int x){
 	int v = f[0][u];

	merge(rt[u][x],rt[u][x],ed[u]);
	merge(rt[u][x],st[u],rt[u][x]);
	dtcl(rt[u][x] = sert(rt[u][x]) , x);

	dtpath(st[v]);
	if(col[st[v]] != x){
		dtrt(rt[u][x] , v);
		merge(rt[v][x],rt[v][x],rt[u][x]);
		xsz[st[v]][x] ++;
	}
	else{
		int p = rot[st[v]] , a , b;
		dtrt(rt[u][x] , p);
		split(rt[p][x] , a , b , st[v]);
		merge(rt[p][x] , a , rt[u][x]);
		merge(rt[p][x] , rt[p][x] , b);
	}
	splay(st[v],0);
	rt[u][x] = 0;
}

void del(int u,bool flg = 1){
	dtpath(st[u]);
	int x = col[st[u]];
	int p = rot[st[u]] , a , b , c;
	
	split(rt[p][x],a,rt[u][x],c,st[u],ed[u]);
	merge(rt[p][x] , a , c);
	serk(st[f[0][u]]);
	if(col[st[f[0][u]]] != x){
		xsz[st[f[0][u]]][x] --;
	}
	xsz[st[u]][x] += sz[rt[u][x]][0] - 2;
	
	a = rt[u][x];
	splay(a,0);
	dtrt(rt[u][x],u);
	for(;ch[a][0];a = ch[a][0]);
	splay(a,0);
	b = ch[a][1];
	ch[a][1] = fa[b] = 0;
	upd(a);
	splay(b,0);
	for(;ch[b][1];b = ch[b][1]);
	splay(b,0);
	rt[u][x] = ch[b][0];
	fa[rt[u][x]] = ch[b][0] = 0;
	upd(b);
	
	splay(st[f[0][u]],0);
}

int ar[maxn];

void ser(int u,int x){
	if(rt[(u+1)/2][x])
		ar[++ar[0]] = (u+1)/2;
	if(sz[ch[u][0]][x])
		ser(ch[u][0] , x);
	if(sz[ch[u][1]][x])
		ser(ch[u][1] , x);
}

char End;

int main(){
	
//	cerr << (&End - &Start) / 1024 / 1024  << endl;
	
	freopen("shu.in","r",stdin);
	freopen("shu.out","w",stdout);

	int ts = 0;
	
	read(n);dep[0] = -1;
	memset(tgrt,-1,sizeof tgrt);mn[0] = 0x3f3f3f3f;
	rep(i,1,n) st[i] = i * 2 - 1 , ed[i] = st[i] + 1;
	rep(i,2,n) read(f[0][i]) , dep[i] = dep[f[0][i]] + 1;
	rep(i,1,n) mx[st[i]] = mn[st[i]] = mx[ed[i]] = mn[ed[i]] = dep[i];
	rep(i,1,2*n)  xsz[i][0] = 1 , sz[i][0] = 1;
	rep(j,1,lim-1) rep(i,1,n) f[j][i] = f[j-1][f[j-1][i]];
	rep(i,1,n){
		int x;
		read(x);
		ins(i,x);
	//	rep(i,1,10) printf("@%d %d %d %d\n",i,fa[i],ch[i][0],ch[i][1]);
	}
	int m;read(m);
	for(int op,x,y;m--;){
		read(op),read(x);
		if(op == 1){
			read(y);serk(st[x]);
			if(y != col[st[x]])
				del(x),
				ins(x,y);
		}
		if(op == 2){
			read(y);splay(st[x],0);
			if(y != col[st[x]]){
				
				int u = st[x] , p = Gets(x , rot[u]) , R = rot[u] , cl = col[u];
				int a , b , c;
				split(rt[R][cl],a,b,c,st[p],ed[p]);
				merge(rt[R][cl],a,c);	
				xsz[st[R]][cl] --;
				
				ar[0] = 0;b = sert(b);
				ser(b , y);
				
				rep(i,1,ar[0]){
					int e = ar[i];
					xsz[st[e]][y] = 0;
					swap(rt[e][y] , rt[e][cl]);
					rt[e][cl] = sert(rt[e][cl]);
					dtcl(rt[e][cl] , cl);
					
					int rse = serk(st[e]) , c , d , f;
					split(b,c,d,st[e]);
					merge(b,c,rt[e][cl]),
					merge(b,b,d);
					rt[e][cl] = 0;
					splay(st[e],0);
				}
				
				splay(b,0);
				dtcl(b , y);dtpath(st[R]);
				if(col[st[R]] != y){
					dtrt(b,R);
					merge(rt[R][y],rt[R][y],b);
					xsz[st[R]][y] ++;
				}
				else{
					int p = rot[st[R]] , a , c;
					dtrt(b, p);	
					split(rt[p][y] , a , c , st[R]);
					merge(rt[p][y] , b , c);
					merge(rt[p][y] , a , rt[p][y]);
				}
				splay(st[R],0);
			}
		}
		if(op == 3){
			dtpath(st[x]);
			int u = st[x] , p = Gets(x , rot[u]) , R = rot[u] , cl = col[u];
			int a , b , c;
			split(rt[R][cl],a,b,c,st[p],ed[p]);
			
			b = sert(b);
			print(col[u],' ');
			print(sz[b][0]/2,' ');
			print(mx[b]-mn[b]+1,'\n');
			
			merge(rt[R][cl] , a , b);
			merge(rt[R][cl] , rt[R][cl] , c) ; 
		}
		if(m % 1000 == 0)		
			flush();
	}
}

本文地址：https://blog.csdn.net/qq_35950004/article/details/107604752