bzoj 4399: 魔法少女LJJ 题解

(Updated: )
oi

BZOJ4399

题意

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
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
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
#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
*/