题目大意：第一行有一个正整数m，表示操作个数。 接下来m行，每行先给出1个正整数c。 若c=1，之后一个正整数x，表示新建一个权值为x的节点，并且节点编号为n+1（当前有n个节点）。 若c=2，之后两个正整数a，b，表示在a，b之间连接一条边。 若c=3，之后两个正整数a，x，表示a联通块内原本权值小于x的节点全部变成x。 若c=4，之后两个正整数a，x，表示a联通块内原本权值大于x的节点全部变成x。 若c=5，之后两个正整数a，k，表示询问a所属于的联通块内的第k小的权值是多少。 若c=6，之后两个正整数a，b，表示询问a所属联通块内所有节点权值之积与b所属联通块内所有节点权值之积的大小， 若a所属联通块内所有节点权值之积大于b所属联通块内所有节点权值之积，输出1，否则为0。 若c=7，之后一个正整数a，表示询问a所在联通块大小 若c=8，之后两个正整数a，b，表示断开a，b所连接的边。 若c=9，之后一个正整数a，表示断开a点的所有连边 c<=7
将一个联通块合并删除，可以建权值线段树，动态开点，使用线段树合并。 3、4操作即插入 等于大于/小于x的数的个数 的x，然后将小于/大于x的数全部删除。 6操作可以将乘积转为对数加法（不过好像不转也可以..），反正也只是比较大小.. 好像不写内存回收会爆炸的把..在delete以后一定再赋值成NULL
#include <cstdio> #include <cmath> #include <deque> #define N 400001 #define M 1000000000 using namespace std; deque<void*> recycle; struct Node { Node* ch[2]; int siz; double sum; Node() { ch[0]=ch[1]=NULL; sum=0; siz=0; } void* operator new(size_t) { if(!recycle.empty()) { Node* tmp=(Node*)recycle.back(); recycle.pop_back(); if(tmp->ch[0]) recycle.push_back(tmp->ch[0]); if(tmp->ch[1]) recycle.push_back(tmp->ch[1]); return tmp; } static Node *mempool,*C; if(mempool==C) mempool=(C=new Node[1<<20])+(1<<20); return C++; } void operator delete(void* tmp) { if(tmp) recycle.push_back(tmp); return ; } void maintain() { siz=0, sum=0; if(ch[0]) siz+=ch[0]->siz, sum+=ch[0]->sum; if(ch[1]) siz+=ch[1]->siz, sum+=ch[1]->sum; return ; } }*root[N]; int T,n,pa[N]; inline int find_pa(int x) { return pa[x]==x ? pa[x] : pa[x]=find_pa(pa[x]); } void Insert(Node*& o,int pos,int val,int L,int R) { if(!o) o=new Node(); if(L==R) { o->siz+=val; o->sum=o->siz*log(L); return ; } int mid=L+R>>1; if(pos<=mid) Insert(o->ch[0],pos,val,L,mid); else Insert(o->ch[1],pos,val,mid+1,R); o->maintain(); return ; } void Merge(Node*& x,Node*& y) { if(!y) return ; if(!x) { x=y; return ; } x->siz+=y->siz, x->sum+=y->sum; Merge(x->ch[0],y->ch[0]), Merge(x->ch[1],y->ch[1]); return ; } void Clear(Node*& o,int l,int r,int L,int R) { if(l>r) return ; if(l==L && r==R) { delete(o); o=NULL; return ; } int mid=L+R>>1; if(r<=mid) Clear(o->ch[0],l,r,L,mid); else if(l>mid) Clear(o->ch[1],l,r,mid+1,R); else Clear(o->ch[0],l,mid,L,mid), Clear(o->ch[1],mid+1,r,mid+1,R); o->maintain(); return ; } int Query_siz(Node* o,int l,int r,int L,int R) { if(l>r || !o) return 0; if(l==L && r==R) return o->siz; int mid=L+R>>1; if(r<=mid) return Query_siz(o->ch[0],l,r,L,mid); if(l>mid) return Query_siz(o->ch[1],l,r,mid+1,R); return Query_siz(o->ch[0],l,mid,L,mid)+Query_siz(o->ch[1],mid+1,r,mid+1,R); } int Query_Kth(Node* o,int x,int L,int R) { if(L==R) return L; if(!o) return -1; if(o->siz<x) return -1; int mid=L+R>>1; int lsiz=o->ch[0] ? o->ch[0]->siz : 0; if(lsiz>=x) return Query_Kth(o->ch[0],x,L,mid); return Query_Kth(o->ch[1],x-lsiz,mid+1,R); } int main() { for(scanf("%d",&T);T;T--) { int mode,x,y; scanf("%d",&mode); switch(mode) { case 1: { scanf("%d",&x); Insert(root[++n],x,1,1,M); pa[n]=n; break; } case 2: { scanf("%d%d",&x,&y); x=find_pa(x), y=find_pa(y); if(x==y) continue; if(root[x]->siz<root[y]->siz) swap(x,y); pa[y]=x; Merge(root[x],root[y]); break; } case 3: { scanf("%d%d",&x,&y); x=find_pa(x); int z=Query_siz(root[x],1,y-1,1,M); Insert(root[x],y,z,1,M); Clear(root[x],1,y-1,1,M); break; } case 4: { scanf("%d%d",&x,&y); x=find_pa(x); int z=Query_siz(root[x],y+1,M,1,M); Insert(root[x],y,z,1,M); Clear(root[x],y+1,M,1,M); break; } case 5: { scanf("%d%d",&x,&y); x=find_pa(x); printf("%d\n",Query_Kth(root[x],y,1,M)); break; } case 6: { scanf("%d%d",&x,&y); x=find_pa(x), y=find_pa(y); printf("%d\n",root[x]->sum>root[y]->sum); break; } case 7: { scanf("%d",&x); x=find_pa(x); printf("%d\n",root[x]->siz); break; } } } return 0; }