[文章目录]
Description
1.新建一个节点，权值为x。
2.连接两个节点。
3.将一个节点a所属于的联通快内权值小于x的所有节点权值变成x。
4.将一个节点a所属于的联通快内权值大于x的所有节点权值变成x。
5.询问一个节点a所属于的联通块内的第k小的权值是多少。
6.询问一个节点a所属联通快内所有节点权值之积与另一个节点b所属联通快内所有节点权值之积的大小。
7.询问a所在联通快内节点的数量
0<=m<=400000,c<=7,所有出现的数均<=1000000000
达成成就：获得新外号 LJJ!!!（神**魔法少女）
有查询第k大，有合并。有修改，还是明显告诉你是线段树的打标记修改为空。直接动态开点+权值线段树合并，并查集维护所在联通块的根。注意，merge(x,y)不一定一直返回x，当x为空的时候会返回y。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 401000
const int inf=1000000000;
inline void read(int &x)
{
x=0; char ch=getchar(); int f=1;
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=f;
}
int n,m,tot,rt[M],fa[M];
int find(int x){return (x==fa[x])?x:(fa[x]=find(fa[x]));}
struct seg
{
int siz,ls,rs;
double sl;
bool lz;
}s[M*17];
inline void clear(int x)
{
if(!x) return ;
s[x].siz=0; s[x].sl=0; s[x].lz=1;
}
inline void pushdown(int x)
{
if(s[x].lz) clear(s[x].ls),clear(s[x].rs),s[x].lz=0;
}
inline void pushup(int x)
{
s[x].siz=s[s[x].ls].siz+s[s[x].rs].siz;
s[x].sl=s[s[x].ls].sl+s[s[x].rs].sl;
}
int merge(int x,int y)
{
if(!s[x].siz||!s[y].siz) return (s[x].siz)?x:y;
pushdown(x); pushdown(y);
s[x].siz+=s[y].siz; s[x].sl+=s[y].sl;
s[x].ls=merge(s[x].ls,s[y].ls);
s[x].rs=merge(s[x].rs,s[y].rs);
return x;
}
void insert(int l,int r,int &root,int w,int z)
{
if(!root) root=++tot; s[root].siz+=z; s[root].sl+=log(w)*z;
if(l==r) return ; pushdown(root); int mid=(l+r)>>1;
if(w<=mid) insert(l,mid,s[root].ls,w,z);
else insert(mid+1,r,s[root].rs,w,z);
}
void fix(int l,int r,int root,int x,int y)
{
if(!s[root].siz) return ;
if(x<=l&&y>=r){
s[root].siz=0; s[root].sl=0; s[root].lz=1;
return ;
}
int mid=(l+r)>>1; pushdown(root);
if(y<=mid) fix(l,mid,s[root].ls,x,y);
else if(x>mid) fix(mid+1,r,s[root].rs,x,y);
else fix(l,mid,s[root].ls,x,y),fix(mid+1,r,s[root].rs,x,y);
pushup(root);
}
int query_w(int l,int r,int root,int x)
{
if(l==r) return l;
int tmp=s[s[root].ls].siz,mid=(l+r)>>1;
if(x<=tmp) return query_w(l,mid,s[root].ls,x);
return query_w(mid+1,r,s[root].rs,x-tmp);
}
int main()
{
read(m); int sw,x,y,z;
while(m--)
{
read(sw);
switch(sw)
{
case 1:
{
read(x); ++n; fa[n]=n;
insert(0,inf,rt[n],x,1); break;
}
case 2:
{
read(x); read(y); x=find(x); y=find(y);
if(x==y) break;
merge(rt[x],rt[y]); fa[y]=x;
break;
}
case 3:
{
read(x); x=find(x); read(y);
z=s[rt[x]].siz; fix(0,inf,rt[x],0,y); z-=s[rt[x]].siz;
insert(0,inf,rt[x],y,z);
break;
}
case 4:
{
read(x); x=find(x); read(y);
z=s[rt[x]].siz; fix(0,inf,rt[x],y,inf); z-=s[rt[x]].siz;
insert(0,inf,rt[x],y,z);
break;
}
case 5:
{
read(x); x=find(x); read(y);
printf("%d\n",query_w(0,inf,rt[x],y));
break;
}
case 6:
{
read(x); read(y); x=find(x); y=find(y);
if(s[rt[x]].sl>s[rt[y]].sl) puts("1");
else puts("0");
break;
}
case 7:
{
read(x); x=find(x); printf("%d\n",s[rt[x]].siz);
break;
}
default : break;
}
}
return 0;
}