bzoj 4399: 魔法少女LJJ 题解

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

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

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

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

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;

}

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

近期文章

近期评论

文章归档

Link

题意

Description

Input

Sample Input

Sample Output

HINT

思路

Code

评论

发送评论编辑评论

Link

题意

Description

Input

Sample Input

Sample Output

HINT

思路

Code

评论

发送评论 编辑评论

发送评论编辑评论