题意：有⑨种操作 1.新建一个节点，权值为x。 2.连接两个节点。 3.将一个节点a所属于的联通快内权值小于x的所有节点权值变成x。 4.将一个节点a所属于的联通快内权值大于x的所有节点权值变成x。 5.询问一个节点a所属于的联通块内的第k小的权值是多少。 6.询问一个节点a所属联通快内所有节点权值之积与另一个节点b所属联通快内所有节点权值之积的大小。 7.询问a所在联通快内节点的数量 8.若两个节点a，b直接相连，将这条边断开。 9.若节点a存在，将这个点删去。 0<=m<=400000，权值<=1000000000，c<=7
动态图问题（大嘘） 8和⑨操作并不存在。于是由于没有单点修改，比BZOJ2333还要简单。 查询第k大的时候忘了一路下推标记WA了一下午。。。 想刷点水题都刷不动，orz 代码：
#include<cstdio> #include<cmath> #include<cassert> #include<tr1/random> #define gm 400001 using namespace std; struct Istream { static const size_t str=1<<16; char buf[str],*s,*t; Istream():buf(),s(),t(){} char get() {return (s==t)?(t=buf+fread(s=buf,1,str,stdin),*s++):(*s++);} Istream& operator>> (int &x) { x=0;register char c; do c=get(); while(c<'0'||c>'9'); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=get(); return *this; } }cin; struct Ostream { static const size_t str=1<<16; char buf[str],*s,*t; Ostream():buf(),s(buf),t(buf+str){} ~Ostream(){fwrite(buf,1,s-buf,stdout);} void put(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);} Ostream& operator<< (int x) { if(!x) put('0'); else { int a[15],t=1; while(x) a[t++]=x%10,x/=10; while(--t) put(a[t]+'0'); } return *this; } Ostream& operator<< (const char *x) { while(*x) put(*x++); return *this; } }cout; const char *endl="\n"; int m; namespace Treap { tr1::mt19937 rnd; struct node { node *l,*r; int v,w,mark,sz; double vx,sum; node(int x):l(),r(),v(x),w(rnd()),mark(),sz(1),vx(log2(x)),sum(vx){} void cast(int x,const double& __logx) { v=mark=x; vx=__logx,sum=__logx*sz; } void down() { if(mark) { if(l) l->cast(mark,vx); if(r) r->cast(mark,vx); mark=0; } } void up() { sz=1,sum=vx; if(l) sz+=l->sz,sum+=l->sum; if(r) sz+=r->sz,sum+=r->sum; } }; struct pair { node *fi,*se; pair(node *fi=0,node *se=0):fi(fi),se(se){} }; struct treap { private: node *rt; static pair split(node *a,int v) { if(!a) return pair(); a->down(); if(a->v<=v) { pair res=split(a->r,v); a->r=res.fi; a->up(); return pair(a,res.se); } else { pair res=split(a->l,v); a->l=res.se; a->up(); return pair(res.fi,a); } } static node* merge(node *a,node *b) { if(!a) return b; if(!b) return a; if(a->w>b->w) { a->down(); a->r=merge(a->r,b); a->up(); return a; } else { b->down(); b->l=merge(a,b->l); b->up(); return b; } } static node *join(node *a,node *b) { if(!a) return b; if(!b) return a; if(a->w>b->w) { pair p=split(b,a->v); a->down(); a->l=join(a->l,p.fi); a->r=join(a->r,p.se); a->up(); return a; } else { pair p=split(a,b->v); b->down(); b->l=join(b->l,p.fi); b->r=join(b->r,p.se); b->up(); return b; } } public: treap():rt(){} treap(int x):rt(new node(x)){} void join(treap &rhs) { rt=join(rt,rhs.rt);rhs.rt=0; } void lower_limit(int x) { pair p=split(rt,x-1); if(p.fi) p.fi->cast(x,log2(x)); rt=merge(p.fi,p.se); } void upper_limit(int x) { pair p=split(rt,x); if(p.se) p.se->cast(x,log2(x)); rt=merge(p.fi,p.se); } int find_by_order(int k) { node *x=rt; while(x) { x->down(); int cnt=(x->l)?(x->l->sz):0; if(k==cnt+1) return x->v; if(k<=cnt) x=x->l; else k-=cnt+1,x=x->r; } assert(0); } bool operator < (const treap &rhs) const { return rt->sum<rhs.rt->sum; } int size() { return rt->sz; } }; } struct union_set { private: int r[gm]; int tot; public: union_set():r(),tot(){} int push_back() { return r[++tot]=tot; } int find(int x) { return r[x]==x?x:r[x]=find(r[x]); } void set(int x,int y) { r[x]=y; } }s; typedef Treap::treap tree; tree t[gm]; int main() { cin>>m; while(m--) { int a,b,c; cin>>c>>a; if(c!=1&&c!=7) cin>>b; switch(c) { case 1: b=s.push_back(); t[b]=tree(a); break; case 2: a=s.find(a),b=s.find(b); if(a!=b) { s.set(a,b); t[b].join(t[a]); } break; case 3: a=s.find(a); t[a].lower_limit(b); break; case 4: a=s.find(a); t[a].upper_limit(b); break; case 5: a=s.find(a); cout<<t[a].find_by_order(b)<<endl; break; case 6: a=s.find(a),b=s.find(b); cout<<int(t[b]<t[a])<<endl; break; default: a=s.find(a); cout<<t[a].size()<<endl; } } return 0; }