QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#478#249482#7626. Quake and Rebuildship2077grass8cowFailed.2023-12-04 09:27:422023-12-04 09:33:53

Details

Extra Test:

Accepted
time: 194ms
memory: 9036kb

input:

200000 200000
1 1 2 4 5 3 2 7 6 10 4 3 13 7 7 3 13 13 8 5 16 15 17 5 10 14 18 24 22 13 3 7 32 6 27 36 31 16 22 38 14 35 36 4 23 9 1 26 43 25 31 9 48 31 15 1 49 2 55 59 16 16 3 53 5 19 15 14 14 10 51 40 48 58 28 55 49 19 72 53 43 64 10 43 64 8 38 5 44 66 62 69 63 84 95 64 53 36 23 3 60 25 51 55 45 85...

output:

3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

result:

ok 100000 lines

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249482#7626. Quake and Rebuildgrass8cowAC ✓1902ms9980kbC++142.5kb2023-11-12 09:35:212024-11-20 20:28:49

answer

#include<bits/stdc++.h>
using namespace std;
int n,q,f[200100],tag[1010],ok[1010],L[1010],R[1010];
int fa[200100];
const int P=510;
int ip[201000];
int dfn[200010],d[201000];
void build(int t){
	if(ok[t])return;
	for(int i=L[t];i<=R[t];i++){
		fa[i]=i;
		int e=f[i]-tag[t];
		if(e>=L[t])fa[i]=fa[e],d[i]=d[e]+1;
		else d[i]=0;
	}
	ok[t]=1;
	for(int i=L[t];i<=R[t];i++)ok[t]&=(fa[i]==i);
}
int ff(int u){return max(1,f[fa[u]]-tag[ip[u]]);}
int nf(int u){return max(1,f[u]-tag[ip[u]]);}
int lca(int u,int v){
	while(1){
		if(ip[u]<ip[v])swap(u,v);
		if(ip[u]>ip[v]||fa[u]!=fa[v])u=ff(u);
		else break;
	}
	while(u!=v){if(u<v)swap(u,v);u=nf(u);}
	return u;
}
int dep(int u){
	int s=0;while(u!=1)s+=d[u]+1,u=ff(u);
	return s;
}
bool gm[201000],gt[201000];
int be[201000],mm[510][510],ts[510],ans;
void sol(int x){
	bool fl=0;
	for(int i=1;i<=ts[x];i++)fl|=gt[fa[mm[x][i]]],gt[fa[mm[x][i]]]=1;
	if(fl){
		for(int i=R[x];i>=L[x];i--){
			gt[i]=0;
			if(gm[i]){
				ans++;int e=nf(i);
				if(e>=L[x])gm[e]=1;
				else{if(!gm[e])gm[e]=1,mm[ip[e]][++ts[ip[e]]]=e;}
			}
		}
		for(int i=L[x];i<=R[x];i++)gm[i]=0;
	}
	else{
		for(int i=1;i<=ts[x];i++){
			gm[mm[x][i]]=0;
			ans+=d[mm[x][i]]+1,gt[fa[mm[x][i]]]=0;
			int e=ff(mm[x][i]);
			if(!gm[e])gm[e]=1,mm[ip[e]][++ts[ip[e]]]=e;
		}
	}
}
int main(){
	cin>>n>>q;
	for(int i=2;i<=n;i++)scanf("%d",&f[i]),ip[i]=1+(i-2)/P;
	fa[1]=1;
	int now=2,p=0;
	while(now<=n){L[++p]=now;R[p]=min(n,now+P-1);now+=P;}
	for(int i=1;i<=p;i++)build(i);
	while(q--){
		int type,l,r,x;
		scanf("%d",&type);
		if(type==1){
			scanf("%d%d%d",&l,&r,&x);
			int il=ip[l],ir=ip[r];
			if(il==ir){
				int t=il;
				for(int i=l;i<=r;i++)f[i]=max(f[i]-x,1);
				build(t);
			}
			else{
				for(int i=l;i<=R[il];i++)f[i]=max(f[i]-x,1);
				build(il);
				for(int i=L[ir];i<=r;i++)f[i]=max(f[i]-x,1);
				build(ir);
				for(int i=il+1;i<ir;i++)tag[i]=min(tag[i]+x,n),build(i);
			}
		}
		else{
			scanf("%d",&x);
			for(int i=1;i<=x;i++)scanf("%d",&be[i]);
			int lc=be[1];for(int i=2;i<=x;i++)lc=lca(lc,be[i]);
			if(x>P){
				for(int i=1;i<=x;i++)gm[be[i]]=1;
				ans=1;
				for(int i=n;i>=2;i--)if(gm[i])ans++,gm[nf(i)]=1;
				memset(gm,0,sizeof(gm));
				printf("%d\n",ans-dep(lc));continue;
			}
			else{
				ans=1;
				memset(ts,0,sizeof(ts));
				for(int i=1;i<=x;i++)if(!gm[be[i]])
				gm[be[i]]=1,ts[ip[be[i]]]++,mm[ip[be[i]]][ts[ip[be[i]]]]=be[i];
				for(int i=ip[n];i;i--)sol(i);
				printf("%d\n",ans-dep(lc));continue;
			}
		}
	}
	return 0;
}