求助 爆空间

#include<iostream>
#include<queue>
#include<vector>
#define N 10000000
using namespace std;
vector <int>V[N];
int pre[N],root[N];
int Front[N],Last[N],t[N];
int n,q;
struct Node{
  int l,r;
  int ls,rs;
  int w;
}tree[N];
queue <int>Q;
int cnt;
int build(int l,int r)
{
  int id=++cnt;
  tree[id].l=l,tree[id].r=r;
  return id;
}
int m,Vsize;
void Insert(int now,int pos,int w)
{
  if(tree[now].l==tree[now].r&&tree[now].l==pos)
    {tree[now].w+=w;return ;}
  int mid=(tree[now].l+tree[now].r)/2;
  if(pos<=mid)
  {
    if(tree[now].ls==0) tree[now].ls=build(tree[now].l,mid);
	Insert(tree[now].ls,pos,w);
  }
  else
  {
    if(tree[now].rs==0) tree[now].rs=build(mid+1,tree[now].r);
	Insert(tree[now].rs,pos,w);
  }
  tree[now].w=(tree[tree[now].ls].w+tree[tree[now].rs].w);
}
int Query(int l,int r)
{
  if(l==r)
  {
    int Size=0;
    for(int i=1;i<=m;i++)
	  Size+=tree[t[i]].w;
	if(Size>Vsize/2) return l;
	return -1;
  }
  int Lsize=0,Rsize=0,mid=(l+r)/2;
  for(int i=1;i<=m;i++)
    Lsize+=tree[tree[t[i]].ls].w;
  if(Lsize>Vsize/2)
  {
    for(int i=1;i<=m;i++)
	  t[i]=tree[t[i]].ls;
	return Query(l,mid);
  }
  for(int i=1;i<=m;i++)
    Rsize+=tree[tree[t[i]].rs].w;
  if(Rsize>Vsize/2)
  {
    for(int i=1;i<=m;i++)
	  t[i]=tree[t[i]].rs;
	return Query(mid+1,r);
  }
  return -1;
}
int merge(int x,int y)
{
  if(!x||!y)
    return x+y;
  if(tree[x].l==tree[x].r)
  {
    tree[x].w+=tree[y].w;
	return x;
  }
  tree[x].ls=merge(tree[x].ls,tree[y].ls);
  tree[x].rs=merge(tree[x].rs,tree[y].rs);
  tree[x].w=tree[tree[x].ls].w+tree[tree[x].rs].w;
  return x;
}
int main()
{
  ios::sync_with_stdio(false);
  freopen("In.in","r",stdin);
  freopen("Out.out","w",stdout);
  cin>>n>>q;
  for(int i=1;i<=n;i++)
  {
    int l;
	cin>>l;
	pre[i]=i,Front[i]=i,Last[i]=i;
	root[i]=build(1,1000000);
	for(int j=1;j<=l;j++)
	{
	  int x;
	  cin>>x;
	  V[i].push_back(x);
	  Insert(root[i],x,1);
	}
  }
  for(int i=1;i<=q;i++)
  {
    int id;
	cin>>id;
	if(id==1)
	{
	  int x,y;
	  cin>>x>>y;
	  V[Last[x]].push_back(y);
	  Insert(root[x],y,1);
	}
	if(id==2)
	{
	  int x;
	  cin>>x;
	  int k=V[Last[x]][V[Last[x]].size()-1];
	  Insert(root[x],k,-1);
	  V[Last[x]].pop_back();
	  if(V[Last[x]].empty())
	    Last[x]=pre[Last[x]];
	}
	if(id==3)
	{
	  Vsize=0,cin>>m;
	  for(int j=1;j<=m;j++)
	  {
	    cin>>t[j];
		t[j]=root[t[j]],Vsize+=tree[t[j]].w;
	  }
	  int Ans=Query(1,1000000);
	  cout<<Ans<<endl;
	}
    if(id==4)
    {
	  int x,y,z;
	  cin>>x>>y>>z;
	  root[z]=merge(root[x],root[y]);
	  pre[Front[y]]=Last[x];
	  Front[z]=Front[x],Last[z]=Last[y];
	}	
  }
}