Description：

支持以下操作：

若 $c=1$ ，表示新建一个权值为 $x$ 的节点。

若 $c=2$ ，表示在 $a,b$ 之间连接一条边。

若 $c=3$ ，表示 $a$ 联通快内原本权值小于 $x$ 的节点全部变成 $x$ 。

若 $c=4$ ，表示 $a$ 联通快内原本权值大于 $x$ 的节点全部变成 $x$ 。

若 $c=5$ ，表示询问 $a$ 所属于的联通块内的第 $k$ 小的权值是多少。

若 $c=6$ ，表示询问 $a$ 所属联通快内所有节点权值之积与 $b$ 联通快内所有节点权值之积的大小。

若 $c=7$ ，表示询问 $a$ 所在联通块大小。

若 $c=8$ ，表示断开 $a,b$ 所连接的边。

若 $c=9$ ，表示断开a点的所有连边。

$1\le n \le 400000,1\le c \le 7$

Solution：

由于 $c\le 7$ 所以所有删边操作都是不存在的，只有加边，这题其实是权值线段树维护动态图， $c=2$ 就是线段树合并， $3,4$ 都是线段树区间清零单点修改操作， $5$ 像主席树一样查， $7$ 也很简单，对于操作 $6$ ，可以维护 $\log$ 的值，就避免了爆 $\text{long long}$ 的情况。

空间真是玄学。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define LEF 1

#define RIG 1000000000

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,q;

#define MAXN 400001

int f[MAXN];

int find(int x){return (f[x] == x ? x : f[x] = find(f[x]));}

struct node

{

	int lc,rc;

	int tot;

	bool tag;

	double sum;

	node(){tot = 0;tag = false;sum = 0;}

}t[MAXN * 15];

int ptr = 0; 

int newnode(){return ++ptr;}

int root[MAXN];

#define mid ((l + r) >> 1)

void pushdown(int rt)

{

	if(t[rt].tag == false)return;

	if(t[rt].lc != 0){t[t[rt].lc].tag = true;t[t[rt].lc].tot = 0;t[t[rt].lc].sum = 0;}

	if(t[rt].rc != 0){t[t[rt].rc].tag = true;t[t[rt].rc].tot = 0;t[t[rt].rc].sum = 0;}

	t[rt].tag = false;

	return;

}

void insert(int &rt,int p,int k,int l,int r)

{

	if(rt == 0)rt = newnode();

	if(l == r)

	{

		t[rt].tot += k;

		t[rt].sum = t[rt].tot * log2(l);

		return;

	}

	pushdown(rt);

	if(p <= mid)insert(t[rt].lc,p,k,l,mid);

	else insert(t[rt].rc,p,k,mid + 1,r);

	t[rt].tot = 0;t[rt].sum = 0;

	if(t[rt].lc != 0)

	{

		t[rt].tot += t[t[rt].lc].tot;

		t[rt].sum += t[t[rt].lc].sum;

	}

	if(t[rt].rc != 0)

	{

		t[rt].tot += t[t[rt].rc].tot;

		t[rt].sum += t[t[rt].rc].sum;

	}

	return;

}

int merge(int x,int y,int l,int r)

{

	if(!x)return y;if(!y)return x;

	pushdown(x);pushdown(y);

	t[x].tot += t[y].tot;t[x].sum += t[y].sum;

	if(l == r)return x;

	t[x].lc = merge(t[x].lc,t[y].lc,l,mid);

	t[x].rc = merge(t[x].rc,t[y].rc,mid + 1,r);

	return x;

}

int qry(int rt,int L,int R,int l,int r)

{

	if(rt == 0)return 0;

	if(L <= l && r <= R)return t[rt].tot;

	int res = 0;pushdown(rt);

	if(L <= mid)res += qry(t[rt].lc,L,R,l,mid);

	if(R > mid)res += qry(t[rt].rc,L,R,mid + 1,r);

	return res;

}

void clr(int rt,int L,int R,int l,int r)

{

	if(rt == 0)return;

	if(L <= l && r <= R)

	{

		t[rt].tag = true;t[rt].tot = 0;t[rt].sum = 0;

		return;

	}

	if(t[rt].tag)return;

	if(L <= mid)clr(t[rt].lc,L,R,l,mid);

	if(R > mid)clr(t[rt].rc,L,R,mid + 1,r);

	return;

}

int findkth(int rt,int k,int l,int r)

{

	if(l == r)return l;

	pushdown(rt);

	int ls = (t[rt].lc == 0 ? 0 : t[t[rt].lc].tot);

	if(k > ls)return findkth(t[rt].rc,k - ls,mid + 1,r);

	else return findkth(t[rt].lc,k,l,mid);

}

int main()

{

	scanf("%d",&q);

	register int opt,a,b;

	n = 0;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d",&opt);

		if(opt == 1)

		{

			a = read();

			++n;f[n] = n;

			insert(root[n],a,1,LEF,RIG);

		}

		if(opt == 2)

		{

			a = read();b = read();

			int p = find(a),q = find(b);

			if(p == q)continue;

			root[q] = merge(root[q],root[p],LEF,RIG);

			f[p] = q;

		}

		if(opt == 3)

		{

			a = read();b = read();a = find(a);

			int cnt = qry(root[a],LEF,b - 1,LEF,RIG);

			clr(root[a],LEF,b - 1,LEF,RIG);

			insert(root[a],b,cnt,LEF,RIG);

		}

		if(opt == 4)

		{

			a = read();b = read();a = find(a);

			int cnt = qry(root[a],b + 1,RIG,LEF,RIG);

			clr(root[a],b + 1,RIG,LEF,RIG);

			insert(root[a],b,cnt,LEF,RIG);

		}

		if(opt == 5)

		{

			a = read();b = read();a = find(a);

			printf("%d\n",findkth(root[a],b,LEF,RIG));

		}

		if(opt == 6)

		{

			a = read();b = read();

			a = find(a);b = find(b);

			printf("%d\n",(t[root[a]].sum > t[root[b]].sum ? 1 : 0));

		}

		if(opt == 7)

		{

			a = read();a = find(a);

			printf("%d\n",t[root[a]].tot);

		}

	}

	return 0;

}