在森林中见过会动的树,在沙漠中见过会动的仙人掌过后,魔法少女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很郁闷,你能帮帮他吗
第一行有一个正整数m,表示操作个数。 接下来m行,每行先给出1个正整数c。 若c=1,之后一个正整数x,表示新建一个权值为x的节点,并且节点编号为n+1(当前有n个节点)。 若c=2,之后两个正整数a,b,表示在a,b之间连接一条边。 若c=3,之后两个正整数a,x,表示a联通快内原本权值小于x的节点全部变成x。 若c=4,之后两个正整数a,x,表示a联通快内原本权值大于x的节点全部变成x。 若c=5,之后两个正整数a,k,表示询问a所属于的联通块内的第k小的权值是多少。 若c=6,之后两个正整数a,b,表示询问a所属联通快内所有节点权值之积与b所属联通快内所有节点权值之积的大小, 若a所属联通快内所有节点权值之积大于b所属联通快内所有节点权值之积,输出1,否则为0。 若c=7,之后一个正整数a,表示询问a所在联通块大小 若c=8,之后两个正整数a,b,表示断开a,b所连接的边。 若c=9,之后一个正整数a,表示断开a点的所有连边 具体输出格式见样例
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<=m<=400000,c<=7,所有出现的数均<=1000000000,所有出现的点保证存在 请认真阅读题面
一看感觉很不可做啊(事实上的确很不可做 然后HINT说要认真阅读题面,然后恍然发现**c<=7c=1,新建一个节点为n+1。 对于c=2,连接两个联通块,用并查集和线段树合并做 对于c=3,权值线段树基本操作 对于c=4,权值线段树基本操作 对于c=5,权值线段树基本操作 对于c=6,把权值转换成对数,log_2(x\times y)=log_2x+log_2y 对于c=7,询问a连通块内根节点的size
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
#define re register
#define LD double
//#define int long long
#define gc getchar
#define mod 100000007
#define MAXN 400010*18
class Quick_Input_Output{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
char Rd[S],*A,*B;
#define pc putchar
public:
// #undef gc
// #define gc tc
inline int read(){
int res=0,f=1;char ch=gc();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
return res*f;
}
inline void write(int x){
if(x<0) pc('-'),x=-x;
if(x<10) pc(x+'0');
else write(x/10),pc(x%10+'0');
}
// #undef gc
#undef pc
}I;
#define File freopen("4399.in","r",stdin);freopen("4399.out","w",stdout);
struct Question{int id,x,y;}q[MAXN];
int m,cnt;
class Discretization{
public:
int lsh[MAXN],n;
inline void init(){
for(int i=1;i<=m;i++){
if(q[i].id==3q[i].id==4) lsh[++n]=q[i].y;
if(q[i].id==1) lsh[++n]=q[i].x;
}
sort(lsh+1,lsh+n+1);
n=unique(lsh+1,lsh+n+1)-(lsh+1);
}
inline int getlsh(int x){
return lower_bound(lsh+1,lsh+n+1,x)-lsh;
}
}L;
class Segment_tree{
public:
int rt[MAXN],sz[MAXN],son[MAXN][2],tag[MAXN],tot;
LD sum[MAXN];
inline void Upd(int x){
sz[x]=sz[son[x][0]]+sz[son[x][1]];
sum[x]=sum[son[x][0]]+sum[son[x][1]];
}
inline void Psd(int x){
if(tag[x]==0) return ;
tag[son[x][0]]=1;sz[son[x][0]]=sum[son[x][0]]=0;
tag[son[x][1]]=1;sz[son[x][1]]=sum[son[x][1]]=0;
tag[x]=0;
}
inline void insert(int x,int l,int r,int now,int sm,LD logsum){
re int mid=l+r>>1;
Psd(x);
if(l==r){
sz[x]=sm;
sum[x]=logsum;
return ;
}
if(now<=mid) insert(son[x][0]==0?son[x][0]=++tot:son[x][0],l,mid,now,sm,logsum);
else insert(son[x][1]==0?son[x][1]=++tot:son[x][1],mid+1,r,now,sm,logsum);
Upd(x);
}
inline int merge(int x,int y,int l,int r){
if(x==0y==0) return x+y;
sum[x]+=sum[y];
sz[x]+=sz[y];
re int mid=l+r>>1;
if(l==r) return x;
Psd(x);Psd(y);
son[x][0]=merge(son[x][0],son[y][0],l,mid);
son[x][1]=merge(son[x][1],son[y][1],mid+1,r);
return x;
}
inline int query(int x,int l,int r,int L,int R){
if(x==0) return 0;
if(L<=l&&r<=R) return sz[x];
re int mid=l+r>>1;
Psd(x);
re int s=0;
if(L<=mid) s+=query(son[x][0],l,mid,L,R);
if(R>mid) s+=query(son[x][1],mid+1,r,L,R);
return s;
}
inline void add(int x,int l,int r,int L,int R){
if(x==0) return ;
if(L<=l&&r<=R){
sum[x]=sz[x]=0;
tag[x]=1;
return ;
}
re int mid=l+r>>1;
Psd(x);
if(L<=mid) add(son[x][0],l,mid,L,R);
if(R>mid) add(son[x][1],mid+1,r,L,R);
Upd(x);
}
inline int getsz(int now,int l,int r,int x){
if(l==r) return L.lsh[l];
re int mid=l+r>>1;
Psd(now);
if(sz[son[now][0]]>=x) return getsz(son[now][0],l,mid,x);
else return getsz(son[now][1],mid+1,r,x-sz[son[now][0]]);
}
}T;
class Union_Checking_Set{
public:
int fa[MAXN];
inline int getfa(int x){
return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
inline void merge(int x,int y){
x=getfa(x);y=getfa(y);
if(x==y) return ;
fa[y]=x;T.rt[x]=T.merge(T.rt[x],T.rt[y],1,L.n);
}
}U;
class Solve{
public:
inline void init(){
m=I.read();
for(int i=1;i<=m;i++){
q[i].id=I.read();
if(q[i].id==1q[i].id==7) q[i].x=I.read();
else q[i].x=I.read(),q[i].y=I.read();
}
L.init();
}
inline void solve(){
for(int x,y,s,i=1;i<=m;i++){
switch(q[i].id){
case 1:++cnt,T.insert(T.rt[cnt]==0?T.rt[cnt]=++T.tot:T.rt[cnt],1,L.n,L.getlsh(q[i].x),1,log2(q[i].x)),U.fa[cnt]=cnt;break;
case 2:U.merge(q[i].x,q[i].y);break;
case 3:x=U.getfa(q[i].x),y=L.getlsh(q[i].y),s=T.query(T.rt[x],1,L.n,1,y),T.add(T.rt[x],1,L.n,1,y),T.insert(T.rt[x]==0?T.rt[x]=++T.tot:T.rt[x],1,L.n,y,s,s*log2(q[i].y));break;
case 4:x=U.getfa(q[i].x),y=L.getlsh(q[i].y),s=T.query(T.rt[x],1,L.n,y,L.n),T.add(T.rt[x],1,L.n,y,L.n),T.insert(T.rt[x]==0?T.rt[x]=++T.tot:T.rt[x],1,L.n,y,s,s*log2(q[i].y));break;
case 5:I.write(T.getsz(T.rt[U.getfa(q[i].x)],1,L.n,q[i].y)),putchar('\n');break;
case 6:I.write(T.sum[T.rt[U.getfa(q[i].x)]]>T.sum[T.rt[U.getfa(q[i].y)]]?1:0),putchar('\n');break;
default:I.write(T.sz[T.rt[U.getfa(q[i].x)]]),putchar('\n');break;
}
}
}
}S;
int main(){
File
S.init();
S.solve();
return 0;
}
/*
11
1 2
1 3
1 4
1 5
1 6
2 1 2
2 2 3
2 3 4
2 4 5
3 2 5
5 3 4
*/