自动搬运

查看原文

来自洛谷，原作者为

	gyh20 orz Feecle6418

搬运于2025-08-24 22:06:44，当前版本为作者最后更新于2021-03-15 08:02:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个很 naive 的做法。

首先，可以先建出操作树，及对于第 $i$ 次操作，若为 $2$，$x$ 向 $i$ 连边，否则 $i-1$ 向 $i$ 连边，然后我们可以在树上 DFS 一遍求出所有答案。

也就是说，我们要支持连边删边和动态维护连通块内权值信息。

将权值离散化，由于后加进来的边一定先删，考虑并查集+分块，维护连通块中每一块的每一种权值个数。

这样的时空复杂度均为 $O(n\sqrt n)$，由于毒瘤的空间被卡掉了。

但您可以直接把块长调为 $20$，然后我 T 了一个点。

但我们可以把分块的数组开成 short，因为 $n/$块大小 不会炸 short，我们便可以调块长为 $40$，可以轻松通过。

#include<cstdio>
#include<algorithm>
#define re register
using namespace std;
#define gc getchar
inline int read(){
	re int t=0;re char v=gc();
	while(v<'0')v=gc();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
	return t;
}
int n,m,A[100002],B[100002],head[100002],cnt,ans[100002],blk,K,fa[100002],sz[100002];
short f[100002][47];
char typ[100002];
struct edge{int to,next;}e[100002];
struct node{int x,y;bool operator <(const node &a)const{return x<a.x;};}p[100002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
inline int root(re int x){return x==fa[x]?x:root(fa[x]);}
inline void dfs(re int x){
	re bool kk=0;
	if(typ[x]==1){
		A[x]=root(A[x]),B[x]=root(B[x]);
		if(A[x]^B[x]){
			kk=1;
			if(sz[A[x]]>sz[B[x]])A[x]^=B[x]^=A[x]^=B[x];
			fa[A[x]]=B[x],sz[B[x]]+=sz[A[x]];
			for(re int i=1;i<=K;++i)f[B[x]][i]+=f[A[x]][i];
		}
	}
	else if(typ[x]==3){
		re int s=B[x],y=0,R=root(A[x]);
		if(s>sz[R])ans[x]=-1;
		else{
			for(re int i=1;i<=K&&!y;++i){
				if(s>f[R][i])s-=f[R][i];
				else y=i;
			}
			for(re int i=(y-1)*blk+1;i<=y*blk&&s;++i)if(root(p[i].y)==R)--s,ans[x]=p[i].x;
		}
	}
	for(re int i=head[x];i;i=e[i].next)dfs(e[i].to);
	if(kk){
		for(re int i=1;i<=K;++i)f[B[x]][i]-=f[A[x]][i];
		fa[A[x]]=A[x],sz[B[x]]-=sz[A[x]];
	}
}
int main(){
	n=read(),m=read(),blk=46,blk=n/blk,K=(n-1)/blk+1;
	for(re int i=1;i<=n;++i)p[i]=(node){read(),i},sz[fa[i]=i]=1;
	sort(p+1,p+n+1);
	for(re int i=1;i<=n;++i){
		re int x=(i-1)/blk+1;
		++f[p[i].y][x];
	}
	for(re int i=1;i<=m;++i){
		typ[i]=read();
		if(typ[i]==1)add(i-1,i),A[i]=read(),B[i]=read();
		else if(typ[i]==2)add(read(),i);
		else add(i-1,i),A[i]=read(),B[i]=read();
	}
	dfs(0);
	for(re int i=1;i<=m;++i)if(typ[i]==3)printf("%d\n",ans[i]);
}