Link
题意
Description
在森林中见过会动的树,在沙漠中见过会动的仙人掌过后,魔法少女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很郁闷,你能帮帮他吗
Input
第一行有一个正整数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点的所有连边
具体输出格式见样例
Sample Input
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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 |
Sample Output
1 2 |
6 |
HINT
对100%的数据 0<=m<=400000,c<=7,所有出现的数均<=1000000000,所有出现的点保证存在
请认真阅读题面
思路
一看感觉很不可做啊(事实上的确很不可做
然后$HINT$说要认真阅读题面,然后恍然发现$c<=7$
对于$c=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$
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 |
#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==3||q[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==0||y==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==1||q[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 */ |
Mod