题目
【题目描述】
在森林中见过会动的树，在沙漠中见过会动的仙人掌过后，魔法少女 LJJ 已经觉得自己见过世界上的所有稀奇古怪的事情了。
LJJ 感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味；小猴在枝头悠来荡去,好不自在；各式各样的鲜花争相开放,各种树枝的枝头挂满沉甸甸的野果；鸟儿的歌声婉转动听,小河里飘着落下的花瓣真是人间仙境”。
SHY 觉得 LJJ 还是太 naive，一天, SHY 带着自己心爱的图找到 LJJ，对 LJJ 说：“既然你已经见识过动态树，动态仙人掌了，那么今天就来见识一下动态图吧”。
LJJ：“要支持什么操作？”
SHY：
1. 新建一个节点，权值为 $x$。
2. 连接两个节点。
3. 将一个节点 $a$ 所属于的联通快内权值小于 $x$ 的所有节点权值变成 $x$。
4. 将一个节点 $a$ 所属于的联通快内权值大于 $x$ 的所有节点权值变成 $x$。
5. 询问一个节点 $a$ 所属于的联通块内的第 $k$ 小的权值是多少。
6. 询问一个节点 $a$ 所属联通快内所有节点权值之积与另一个节点 $b$ 所属联通快内所有节点权值之积的大小。
7. 询问 $a$ 所在联通块内节点的数量
8. 若两个节点 $a$，$b$ 直接相连，将这条边断开。
9. 若节点 $a$ 存在，将这个点删去。
LJJ：“我可以离线吗？”
SHY：“可以，每次操作是不加密的。”
LJJ：“我可以暴力吗？”
SHY：“自重。”
LJJ很郁闷，你能帮帮他吗？
【输入格式】
第一行一个整数 $n$ ，代表岛屿数量。
接下来 $n-1$ 行，每行三个整数 $u,v,w$ ，代表 $u$ 号岛屿和 $v$ 号岛屿由一条代价为 $c$ 的桥梁直接相连，保证 $1 \le u,v \le n$ 且 $1 \le c \le 100000 $ 。
第 $n+1$ 行，一个整数 $m$ ，代表敌方机器能使用的次数。
接下来 $m$ 行，每行一个整数 $k_i$ ，代表第 $i$ 次后，有 $k_i$ 个岛屿资源丰富，接下来 $k$ 个整数$h_1,h_2,…h_k$ ，表示资源丰富岛屿的编号。
【输出格式】
具体输出格式见样例 。
【样例输入】
12
1 2
1 3
1 4
1 5
1 6
2 1 2
2 2 3
2 3 4
2 4 5
9 1
3 2 5
5 3 4
【样例输出】
6
【数据范围与提示】
对 $100\%$ 的数据 $0\le m \le 400000,c \le 7$,所有出现的数均 $\le 1000000000$,所有出现的点保证存在.
题解
题目中 $ c \leq 7 $，即说明仅有前 $ 7 $ 个操作
对于操作一，新建一棵线段树，并插入这个点的值
对于操作二，合并两颗线段树，用并查集维护
对于操作三，查询个数并删除小于 $ x $ 的点，插入 $ x $
对于操作四，类似三
对于操作五，线段树上二分即可
对于操作六，可以发现 $ \log(a\times b)=\log a+\log b $，所以转化成 $ log x $ 比较和即可
对于操作七，查询整个线段树点的个数即可
于是这又是一道大力题
代码
#include<bits/stdc++.h>
#define LL long long
#define db double
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
int R(){
int x;bool f=;char ch;_(!)if(ch=='-')f=;x=ch^;
_()x=(x<<)+(x<<)+(ch^);return f?x:-x;}
const int N=2e6+;
int n,m,tmp,cnt,fa[N],d[N],rot[N];
struct node{int op,x,y;}q[N];
struct seg{int ls,rs,num;bool tag;db val;}tr[N*];
int ef(int x){return lower_bound(d+,d++n,x)-d;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
#define Ls(x) tr[x].ls
#define Rs(x) tr[x].rs
void pushup(int rt){
tr[rt].num=tr[Ls(rt)].num+tr[Rs(rt)].num;
tr[rt].val=tr[Ls(rt)].val+tr[Rs(rt)].val;
return;
}
void pushdown(int rt){
tr[rt].tag=;
tr[Ls(rt)].num=tr[Ls(rt)].val=,tr[Ls(rt)].tag=;
tr[Rs(rt)].num=tr[Rs(rt)].val=,tr[Rs(rt)].tag=;
return;
}
void insert(int &rt,int l,int r,int k,int x,db y){
if(!rt)rt=++cnt;
if(l==r){tr[rt].num+=x,tr[rt].val+=y;return;}
int mid=(l+r)>>;
if(tr[rt].tag)pushdown(rt);
if(k<=mid)insert(Ls(rt),l,mid,k,x,y);
else insert(Rs(rt),mid+,r,k,x,y);
pushup(rt);
return;
}
void merge(int &o1,int o2,int l,int r){
if(!o1||!o2){o1+=o2;return;}
if(l==r){
tr[o1].num+=tr[o2].num,tr[o1].val+=tr[o2].val;
return;
}
int mid=(l+r)>>;
if(tr[o1].tag)pushdown(o1);
if(tr[o2].tag)pushdown(o2);
merge(Ls(o1),Ls(o2),l,mid),merge(Rs(o1),Rs(o2),mid+,r);
pushup(o1);
return;
}
int query(int rt,int l,int r,int ql,int qr){
if(!rt||qr<ql)return ;
if(ql<=l&&qr>=r)return tr[rt].num;
int mid=(l+r)>>,res=;
if(tr[rt].tag)pushdown(rt);
if(ql<=mid)res=query(Ls(rt),l,mid,ql,qr);
if(qr>mid)res+=query(Rs(rt),mid+,r,ql,qr);
return res;
}
void clean(int rt,int l,int r,int ql,int qr){
if(!rt||qr<ql)return;
if(ql<=l&&qr>=r){
tr[rt].num=tr[rt].val=,tr[rt].tag=;
return;
}
int mid=(l+r)>>;
if(ql<=mid)clean(Ls(rt),l,mid,ql,qr);
if(qr>mid)clean(Rs(rt),mid+,r,ql,qr);
pushup(rt);
return;
}
int ask(int rt,int l,int r,int k){
if(l==r)return d[l];
int mid=(l+r)>>;
if(tr[rt].tag)pushdown(rt);
if(k<=tr[Ls(rt)].num)return ask(Ls(rt),l,mid,k);
else return ask(Rs(rt),mid+,r,k-tr[Ls(rt)].num);
}
int main(){
m=R();
for(int i=;i<=m;i++){
int op=R(),x=R(),y=;
if(op!=&&op!=)y=R();
q[i]=(node){op,x,y};
if(op==||op==)d[++n]=y;
if(op==)d[++n]=x;
}
sort(d+,d++n);
n=unique(d+,d++n)-d-;
for(int i=;i<=m;i++){
int op=q[i].op,x=q[i].x,y=q[i].y;
if(op==)insert(rot[++tmp],,n,ef(x),,(db)log(x)),fa[tmp]=tmp;
if(op==){
int fx=find(x),fy=find(y);
if(fx!=fy)fa[fy]=fx,merge(rot[fx],rot[fy],,n);
}
if(op==){
int fx=find(x),k=ef(y),sum=query(rot[fx],,n,,k-);
clean(rot[fx],,n,,k-),insert(rot[fx],,n,k,sum,sum*log(y));
}
if(op==){
int fx=find(x),k=ef(y),sum=query(rot[fx],,n,k+,n);
clean(rot[fx],,n,k+,n),insert(rot[fx],,n,k,sum,sum*log(y));
}
if(op==)printf("%d\n",ask(rot[find(x)],,n,y));
if(op==)puts(tr[rot[find(x)]].val>tr[rot[find(y)]].val?"":"");
if(op==)printf("%d\n",tr[rot[find(x)]].num);
}
return ;
}