弹球弹弹弹

C++14(g++5.4) 解法, 执行用时: 1814ms, 内存消耗: 184288K, 提交时间: 2018-05-25 21:29:06

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=5e5+5;
int n;
int lk[N];vector<int>son[N];
int belong[N],id[N],deep[N],dfn[N],sz[N];
int ccnt,fir[N],len[N],s[N],tot;
#define mid ((l+r)/2)
namespace SEG
{
const int T=N*20+N+N+N;
int cl[T],cr[T],s[T],tot=N+N;
void add(int k,int x)
{
	int l=1,r=n;
	while(1)
	{
		++s[k];
		if(l==r)break;
		if(x<=mid)
		{
			k=cl[k]?cl[k]:cl[k]=++tot;
			r=mid;
		}
		else
		{
			k=cr[k]?cr[k]:cr[k]=++tot;
			l=mid+1;
		}
	}
}
int ans,ql,qr;
void dfs(int k,int l,int r)
{
	if(!s[k])return ;
	if(ql<=l&&qr>=r)
	{
		ans+=s[k];
		return ;
	}
	if(ql<=mid)dfs(cl[k],l,mid);
	if(qr>mid)dfs(cr[k],mid+1,r);
}
int qiu(int k,int l,int r)
{
	ans=0;ql=l;qr=r;
	dfs(k,1,n);
	return ans;
}
};
namespace DFS
{
int tot;
void dfs(int x,int no,int dep)
{
	belong[x]=ccnt;
	deep[x]=dep;id[x]=::tot;
	dfn[x]=++tot;
	sz[x]=1;
	for(auto y:son[x])
	if(y!=no)
	{
		dfs(y,0,dep+1);
		sz[x]+=sz[y];
	}
}
};
void init(int x)
{
	++ccnt;
	while(!belong[x])
	{
		belong[x]=ccnt;
		x=lk[x];
	}
	fir[ccnt]=tot;
	for(int y=lk[x],last=x;;last=y,y=lk[y])
	{
		DFS::dfs(y,last,1);
		++tot;
		if(y==x)break;
	}
	len[ccnt]=tot-fir[ccnt];
}
vector<int>lkq[N];

int main()
{
	//eopen("1.in","r",stdin);
	cin>>n;
	rep(i,1,n)
	{
		scanf("%d",lk+i);
		son[lk[i]].push_back(i);
	}
	rep(x,1,n)
	if(!belong[x])
	{
	//	cerr<<"x="<<x<<endl;
		init(x);
	}
	int m;cin>>m;
	int last=0;
	rep(i,1,m)
	{
		int x;
		scanf("%d",&x);
		x^=last;
		//cerr<<"x="<<x<<endl;
		SEG::add(deep[x]+i,dfn[x]);
		if(i+deep[x]<=m)lkq[i+deep[x]].push_back(x);
		
		for(auto x:lkq[i])
		{
			int b=belong[x];
			++s[fir[b]+(id[x]-fir[b]+len[b]-(i-1)%len[b])%len[b]];
		}
		int b=belong[x];
		last=0;
		if(deep[x]==1)
		last=s[fir[b]+(id[x]-fir[b]+len[b]-i%len[b])%len[b]];
		last+=SEG::qiu(deep[x]+i,dfn[x],dfn[x]+sz[x]-1);
		printf("%d\n",last);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 1043ms, 内存消耗: 27112K, 提交时间: 2018-05-25 22:02:10

#include<stdio.h>
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
const int N=1e6+7;
int _(){
	int x=0,c=getchar();
	while(c<48)c=getchar();
	while(c>47)x=x*10+c-48,c=getchar();
	return x;
}
int n,m,t,la;
int fa[N],in[N],q[N],ql=0,qr=0,c[N],c0[N],ws[N],e0[N],nx[N];
int sz[N],son[N],top[N],len[N],id[N],idp=0,ss[N];
void ins(int i){
	int w=ws[i],z=top[w],d=t+id[w]-id[z];
	++c[c0[i]=id[z]+d%len[z]];
	if(!in[z]&&++d<=m)ws[i]=fa[z],nx[i]=e0[d],e0[d]=i;
}
int que(int w){
	int z=top[w];
	return c[id[z]+(t+id[w]-id[z])%len[z]];
}
int main(){
	n=_();
	assert(1<=n&&n<=500000);
	F(i,1,n)++in[fa[i]=_()],assert(1<=fa[i]&&fa[i]<=n);
	F(i,1,n)if(!in[i])sz[q[++qr]=i]=1;
	while(ql!=qr){
		int w=q[++ql],f=fa[w];
		sz[f]+=sz[w];
		if(sz[w]>sz[son[f]])son[f]=w;
		if(!--in[f])q[++qr]=f;
	}
	for(int i=qr,w;i;--i)if(!top[w=q[i]]){
		for(int u=w;u;u=son[u])top[u]=w,id[u]=++idp;
		len[w]=idp-id[w]+1;
	}
	F(w,1,n)if(in[w]==1){
		int sp=0;
		for(int u=fa[w];in[u]==1;in[u]=2,u=fa[u])top[u]=w,ss[++sp]=u;
		for(len[w]=sp;sp;id[ss[sp--]]=++idp);
	}
	for(m=_(),t=1,assert(1<=m&&m<=500000);t<=m;++t){
		for(int i=e0[t],j;i;j=nx[i],--c[c0[i]],ins(i),i=j);
		int w=ws[t]=_()^la;
		assert(1<=w&&w<=n);
		ins(t);
		printf("%d\n",la=que(w));
//		la=0;
	}
	return 0;
}

详情