求助超时

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000005;
int head[N],tail[N],pre[N],val[N],sz[N];
int id=0;
void pushback(int x,int y){//在序列x后面添加y 
	id++;
	if(!head[x])
		head[x]=id;
	val[id]=y;
	pre[id]=tail[x];
	tail[x]=id;
}
void pop(int x){//解决掉最后一个 
	sz[x]--;
	tail[x]=pre[tail[x]];
	if(sz[x]==0){
		head[x]=0;
	} 
}
int roots[N];
int cnt=0;
struct node{
	int ls;
	int rs;
	int ex;//消除后剩余的颜色 
	int sum;//消除后的sum 
	int siz; //不消除总共的sum。 
}tree[10*N];
void pushupp(int rt){
	tree[rt].siz=tree[tree[rt].ls].siz+tree[tree[rt].rs].siz;
	if(tree[tree[rt].ls].sum>tree[tree[rt].rs].sum){
		tree[rt].sum=tree[tree[rt].ls].sum-tree[tree[rt].rs].sum;
		tree[rt].ex=tree[tree[rt].ls].ex;
	}
	else{
		tree[rt].sum=tree[tree[rt].rs].sum-tree[tree[rt].ls].sum;
		tree[rt].ex=tree[tree[rt].rs].ex;
	}
}
int add(int rt,int le,int ri,int pos,int val){
	if(pos<le||pos>ri){
		return rt;
	}
	if(!rt){
		cnt++;
		rt=cnt;
	}
	if(le==ri){
		tree[rt].sum+=val;
		tree[rt].ex=pos;
		tree[rt].siz+=val;
		return rt;
	}
	int mid=(le+ri)>>1;
	tree[rt].ls=add(tree[rt].ls,le,mid,pos,val);
	tree[rt].rs=add(tree[rt].rs,mid+1,ri,pos,val);
	pushupp(rt);//直接开始消除 
	return rt;
	
}
int merge(int newroot,int roota,int rootb,int le,int ri){//合并操作（不知道是不是对的） 
	if(!roota&&!rootb){
		return newroot;
	}
	if(!newroot){
		cnt++;
		newroot=cnt;	
	}
	int mid=(le+ri)/2; 
	if(!roota){
		tree[newroot]=tree[rootb];
		tree[newroot].ls=merge(tree[newroot].ls,tree[roota].ls,tree[rootb].ls,le,mid);
		tree[newroot].rs=merge(tree[newroot].rs,tree[roota].rs,tree[rootb].rs,mid+1,ri);
		return newroot;
	}
	if(!rootb){
		tree[newroot]=tree[roota];
		tree[newroot].ls=merge(tree[newroot].ls,tree[roota].ls,tree[rootb].ls,le,mid);
		tree[newroot].rs=merge(tree[newroot].rs,tree[roota].rs,tree[rootb].rs,mid+1,ri);
		return newroot;
	}
	
	if(le==ri){
		tree[newroot].ex=tree[roota].ex;
		tree[newroot].sum=tree[roota].sum+tree[rootb].sum;

		tree[newroot].siz=tree[roota].siz+tree[rootb].siz;
		return newroot; 
	}
	tree[newroot].ls=merge(tree[newroot].ls,tree[roota].ls,tree[rootb].ls,le,mid);
	tree[newroot].rs=merge(tree[newroot].rs,tree[roota].rs,tree[rootb].rs,mid+1,ri);
	pushupp(newroot);
	return newroot;
}
int query(int rt,int pos,int le,int ri){
	if(pos<le||pos>ri){
		return 0;
	}
	if(le==ri){
		return tree[rt].sum;
	}
	int ret=0;
	int mid=(le+ri)>>1;
	ret+=query(tree[rt].ls,pos,le,mid);
	ret+=query(tree[rt].rs,pos,mid+1,ri);
	return ret; 
} 
vector<int>vec;
signed main(){
//	freopen("major11.in","r",stdin);
//	freopen("ans.out","w",stdout);
	int n,q;
	scanf("%lld%lld",&n,&q);
	int maxn=n+q;
	int fc=n; 
	for(int i=1;i<=n;i++){
		int m;
		scanf("%lld",&m);
		cnt++;
		roots[i]=cnt;
		for(int j=1;j<=m;j++){
			int u;
			scanf("%lld",&u);
			pushback(i,u);
			add(roots[i],0,maxn,u,1);
			sz[i]++; 
//			printf("test:%lld\n",tree[roots[i]].ex);
		}
	}
	while(q--){
		int op;
		scanf("%lld",&op);
		if(op==1){
			int x,y;
			scanf("%lld%lld",&x,&y);
			pushback(x,y);
			add(roots[x],0,maxn,y,1);
		}
		else if(op==2){
			int x;
			scanf("%lld",&x);
			add(roots[x],0,maxn,val[tail[x]],-1);
			pop(x);
			
		} 
		else if(op==3){
			int m;
			scanf("%lld",&m);
			vec.clear();
			int col=-1;
			int colsum=0;
			for(int i=1;i<=m;i++){
				int u;
				scanf("%lld",&u);
				vec.push_back(u);
				int rt=roots[u];
				if(tree[rt].ex==col){
					colsum+=tree[rt].sum;
				}
				else{
					if(tree[rt].sum>=colsum){
						colsum=tree[rt].sum-colsum;
						col=tree[rt].ex;
					} 
					else{
						colsum=colsum-tree[rt].sum;
					}
				}
			}
			int sum=0;
			int sumsz=0;
			for(int i=0;i<vec.size();i++){
				int rt=roots[vec[i]];
				sum+=query(rt,col,0,maxn);
				sumsz+=tree[rt].siz;
			}
			int seil=floor(1.0*sumsz/2);
			if(sum>seil){
				printf("%lld\n",col);
			} 
			else{
				printf("-1\n");
			}
		}
		else if(op==4){
			int a,b,c;
			scanf("%lld%lld%lld",&a,&b,&c); 
			roots[c]=merge(roots[c],roots[a],roots[b],1,maxn);
			if(tail[b])
				tail[c]=tail[b];
			else
				tail[c]=tail[a];
			if(head[a])
				head[c]=head[a];
			else
				head[c]=head[b];
			if(head[b])
				pre[head[b]]=tail[a];
			sz[c]=sz[a]+sz[b];
			sz[a]=sz[b]=head[a]=head[b]=tail[a]=tail[b]=0;
		}
	}
}