先上头图:
诈骗题认真读题 c<=7
只需要考虑前七个操作
一.动态开点即可
二.线段树合并
三.四.对于这两个操作，可以先统计出有多少个数小于/大于x，然后删除所有小于/大于x的数，并在x位置加上这些数
五.下放标记查询即可
六.每个数最大为1e9，直接乘肯定会炸，所以可以用double存它们的对数之积，log(nm)=log(n)+log(m)的性质可以很好地处理
七.直接查询即可
这题的思路还是非常简单的，主要在码出来
%%%%%%
调了两天半的代码：
#include <bits/stdc++.h>
#define ls tree[gjd].lson
#define rs tree[gjd].rson
using namespace std;
const int N=400010,inf=1e9;
int x,a,b,k,m,ch,tot,cnt;
int fa[N],rt[N];
struct stu{int lson,rson,data;//data 存块数量 double sum;//求和 bool lazy;//标记
}tree[50*N];
int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}void pushup(int gjd){tree[gjd].data=tree[ls].data+tree[rs].data;tree[gjd].sum=tree[ls].sum+tree[rs].sum;
}
void pushdown(int gjd){tree[ls].lazy=tree[rs].lazy=1;tree[ls].data=tree[rs].data=0;tree[ls].sum=tree[rs].sum=0;tree[gjd].lazy=0;
}void insert(int &gjd,int l,int r,int now,int data,double sum){if(!gjd) gjd=++cnt;tree[gjd].sum+=sum;tree[gjd].data+=data;if(l==r) return;if(tree[gjd].lazy) pushdown(gjd);int mid=(l+r)>>1;if(now<=mid) insert(ls,l,mid,now,data,sum);else insert(rs,mid+1,r,now,data,sum);
}int update(int gjd,int l,int r,int x,int y){if(x>y||!gjd) return 0;if(l==x&&r==y){int p=tree[gjd].data;tree[gjd].data=0;tree[gjd].sum=0;tree[gjd].lazy=1;return p;}if(tree[gjd].lazy) pushdown(gjd);int mid=(l+r)>>1,ans;if(y<=mid) ans=update(ls,l,mid,x,y);else if(x>mid) ans=update(rs,mid+1,r,x,y);else ans=update(ls,l,mid,x,mid)+update(rs,mid+1,r,mid+1,y);pushup(gjd);return ans;
}int queryk(int gjd,int l,int r,int k){if(l==r) return l;if(tree[gjd].lazy) pushdown(gjd);int mid=(l+r)>>1;if(k<=tree[ls].data) return queryk(ls,l,mid,k);else return queryk(rs,mid+1,r,k-tree[ls].data);
}int merge(int p,int q,int l,int r){if(!p) return q;if(!q) return p;tree[p].data+=tree[q].data;tree[p].sum+=tree[q].sum;if(l<r){if(tree[p].lazy) pushdown(p);if(tree[q].lazy) pushdown(q);int mid=(l+r)>>1;tree[p].lson=merge(tree[p].lson,tree[q].lson,l,mid);tree[p].rson=merge(tree[p].rson,tree[q].rson,mid+1,r); }return p;
}
int main(){ios::sync_with_stdio(false);cin>>m;while(m--){cin>>ch;//对于操作1、2、3、4、5、7，很容易想到使用并查集维护连通块，//对每个连通块开一棵权值线段树。if(ch==1){cin>>x;fa[++tot]=tot;insert(rt[tot],1,inf,x,1,log(x));}else if(ch==2){cin>>a>>b;a=find(a),b=find(b);if(a!=b) rt[a]=merge(rt[a],rt[b],1,inf);fa[b]=a;}//对于3、4操作，可以先统计出有多少个数小于/大于x，//然后删除所有小于/大于x的数，并在x位置加上这些数else if(ch==3){cin>>a>>x;a=find(a);int down=update(rt[a],1,inf,1,x-1);insert(rt[a],1,inf,x,down,down*log(x));}else if(ch==4){cin>>a>>x;a=find(a);int up=update(rt[a],1,inf,x+1,inf);insert(rt[a],1,inf,x,up,up*log(x));}else if(ch==5){cin>>a>>k;a=find(a);cout<<queryk(rt[a],1,inf,k)<<endl;}//取log(nm)=log(n)+log(m)处理乘法else if(ch==6){cin>>a>>b;a=find(a),b=find(b);if(tree[rt[a]].sum>tree[rt[b]].sum) cout<<"1"<<endl;else cout<<"0"<<endl;}else if(ch==7){cin>>a;a=find(a);cout<<tree[rt[a]].data<<endl;}
// else if(ch==8) cin>>a>>b;
// else if(ch==9) cin>>a;}return 0;
}#一名爱打篮球的oier#
