注意到只有增加点/合并的操作。这些操作都可以用线段树完成，于是线段树合并一发就好了。注意乘积大小直接比较肯定会炸，取个对数即可。数据中存在重边。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 400010 #define inf 1000000000 int m,tot,fa[N],root[N],cnt; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} struct data{int l,r,s;double v;bool f; }tree[N*16]; void up(int k) { tree[k].s=tree[tree[k].l].s+tree[tree[k].r].s; tree[k].v=tree[tree[k].l].v+tree[tree[k].r].v; } void down(int k) { tree[tree[k].l].f=tree[tree[k].r].f=1; tree[tree[k].l].s=tree[tree[k].r].s=0; tree[tree[k].l].v=tree[tree[k].r].v=0; tree[k].f=0; } void ins(int &k,int l,int r,int x,int s,double y) { if (!k) k=++cnt; tree[k].v+=y;tree[k].s+=s; if (l==r) return; if (tree[k].f) down(k); int mid=l+r>>1; if (x<=mid) ins(tree[k].l,l,mid,x,s,y); else ins(tree[k].r,mid+1,r,x,s,y); } int merge(int x,int y,int l,int r) { if (!x||!y) return x|y; tree[x].s+=tree[y].s,tree[x].v+=tree[y].v; if (l<r) { if (tree[x].f) down(x);if (tree[y].f) down(y); int mid=l+r>>1; tree[x].l=merge(tree[x].l,tree[y].l,l,mid); tree[x].r=merge(tree[x].r,tree[y].r,mid+1,r); } return x; } int modify(int k,int l,int r,int x,int y) { if (x>y||!k) return 0; if (l==x&&r==y) { int p=tree[k].s; tree[k].s=0,tree[k].v=0,tree[k].f=1; return p; } if (tree[k].f) down(k); int mid=l+r>>1,ans; if (y<=mid) ans=modify(tree[k].l,l,mid,x,y); else if (x>mid) ans=modify(tree[k].r,mid+1,r,x,y); else ans=modify(tree[k].l,l,mid,x,mid)+modify(tree[k].r,mid+1,r,mid+1,y); up(k); return ans; } int query(int k,int l,int r,int x) { if (l==r) return l; if (tree[k].f) down(k); int mid=l+r>>1; if (tree[tree[k].l].s>=x) return query(tree[k].l,l,mid,x); else return query(tree[k].r,mid+1,r,x-tree[tree[k].l].s); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4399.in","r",stdin); freopen("bzoj4399.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif m=read(); while (m--) { int op=read(); switch(op) { case 1: { fa[++tot]=tot;int x=read(); ins(root[tot],1,inf,x,1,log(x)); break; } case 2: { int x=find(read()),y=find(read()); if (x!=y) root[x]=merge(root[x],root[y],1,inf); fa[y]=x; break; } case 3: { int p=find(read()),x=read(); int s=modify(root[p],1,inf,1,x-1); ins(root[p],1,inf,x,s,s*log(x)); break; } case 4: { int p=find(read()),x=read(); int s=modify(root[p],1,inf,x+1,inf); ins(root[p],1,inf,x,s,s*log(x)); break; } case 5: { int p=find(read()),x=read(); printf("%d ",query(root[p],1,inf,x)); break; } case 6: { int x=find(read()),y=find(read()); printf("%d ",tree[root[x]].v>tree[root[y]].v); break; } case 7: { int x=find(read()); printf("%d ",tree[root[x]].s); break; } } } return 0; }