6.18 省选模拟赛树倍增 LCT

LINK：树

考虑暴力保存每个版本的父亲然后暴力向上跳。得分20.

考虑离线可以离线那么就可以先把树给搞出来然后考虑求k级祖先可以倍增求。

如何判断合法其实要求路径上的边的时间戳<=当前时间戳这个也可以倍增做。

当然我脑抽了把询问版本排序后利用并查集判连通性了。

考虑正解：这下就有两个方向了：

一个是倍增数组的问题容易想到如果倍增数组可以求出那么问题迎刃而解倍增数组每个位置最多被更新一次所以每次暴力判断是否可以更新递归来做这个事情。

复杂度不太能证明。

还有一个是如果可以直接求出k级祖先利用可持久化并查集也可以求出答案。

那么这个k级祖先可以利用LCT来求 access之后暴力在splay上跳。可持久化并查集判定。

第二个询问可以二分一下然后定位然后判定。复杂度nlog^2.

这个做法非常不优美。

还是考虑将判定条件转到路径上的边的出现时间<当前时间来判断。

LCT维护子树内的最大值就可以直接在LCT上跳了。

k级祖先也是如此可以直接跳也可以求出来那部分点再跳。

const int MAXN=100010;

int n,m,T,last,len,now;

int c[MAXN][2],f[MAXN],fa[MAXN],mx[MAXN],sz[MAXN],rev[MAXN],v[MAXN];

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

IV pushup(int x)

{

	sz[x]=sz[l(x)]+sz[r(x)]+1;

	mx[x]=max(v[x],max(mx[l(x)],mx[r(x)]));

}

IV rotate(int x)

{

	int old=f[x],oldf=f[old],k=c[old][1]==x;

	c[old][k]=c[x][k^1];c[x][k^1]=old;

	if(pd(old))c[oldf][c[oldf][1]==old]=x;

	if(c[old][k])f[c[old][k]]=old;

	f[old]=x;f[x]=oldf;pushup(old);

}

IV splay(int x)

{

	while(pd(x))

	{

		int old=f[x];

		if(pd(old))rotate(((c[old][1]==x)^(c[f[old]][1]==old))?x:old);

		rotate(x);

	}

	pushup(x);

}

IV access(int x)

{

	for(int y=0;x;x=f[y=x])

		splay(x),c[x][1]=y,pushup(x);

}

IV LINK(int x,int y)//这里题目中保证了x没有父亲.

{

	access(x);

	splay(x);

	v[x]=now;

	fa[x]=f[x]=y;

	pushup(x);

}

inline int get_mx(int x,int b)

{

	if(mx[x]<=b)return 0;

	while(x)

	{

		if(r(x)&&mx[r(x)]>b)x=r(x);

		else

		{

			if(v[x]>b)return x;

			else x=c[x][0];

		}

	}

	return x;

}

inline int get_Kth(int b,int x,int k)

{

	access(x);

	splay(x);

	int w=get_mx(x,b);

	access(fa[w]);

	splay(x);

	++k;

	if(sz[x]<k)return 0;

	while(x)

	{

		if(sz[r(x)]>=k)x=r(x);

		else

		{

			if(sz[r(x)]+1==k)return x;

			k=k-sz[r(x)]-1;

			x=l(x);

		}

	}

	return x;

}

inline int get_dep(int b,int x)

{

	access(x);

	splay(x);

	int w=get_mx(x,b);

	access(fa[w]);

	splay(x);

	return sz[x]-1;

}

int main()

{

	freopen("1.in","r",stdin);

	//freopen("tree.out","w",stdout);

	get(n);get(m);get(T);

	rep(1,m,i)

	{

		int get(op),u,v,b;now=i;

		op=(op+T*last)%3;

		if(!op)

		{

			get(u);get(v);

			u=(u+T*last)%n+1;

			v=(v+T*last)%n+1;

			LINK(u,v);

		}

		if(op==1)

		{

			get(b);get(u);int get(k);

			b=(b+T*last)%m;

			u=(u+T*last)%n+1;

			k=(k+T*last)%n;

			put(last=get_Kth(b,u,k));

		}

		if(op==2)

		{

			get(b);get(u);

			b=(b+T*last)%m;

			u=(u+T*last)%n+1;

			put(last=get_dep(b,u));

		}

	}

	return 0;

}

巴特西

6.18 省选模拟赛树倍增 LCT

最新文章

热门文章

巴特西

6.18 省选模拟赛 树 倍增 LCT

最新文章

热门文章

6.18 省选模拟赛树倍增 LCT