【日常小测】青青草原播种计划

  • 题目来源：湖师大附中集训Day10T3
  • 本文为博主原创，未经许可不得转载

分析：

首先考虑神秘数的求法：

初始时神秘数为1，然后往里面添加元素

加入一个新数后，如果这个数不超过原神秘数，那么新神秘数就等于当前所有数之和+1

否则，神秘数就不再改变了

所以我们使用权值线段树来维护每一个集合，我们知道权值线段树维护mex很容易实现

考虑线段树如何求神秘数呢

我们发现，如果对于一个子集，这个子集的神秘数等于这个子集的所有元素的和+1，那么我们添加任意的不超过这个神秘数的数，都能保证这个性质仍然被满足

于是我们动态维护神秘数，每次在线段树上查询值小于等于神秘数的元素的和，于是这个和+1就是新的神秘数

由于每2次更新神秘数都至少会使其翻倍，所以最多更新O(logn)次

每次询问神秘数的复杂度是O(log^2n)的

至于操作三就是线段树合并

由于操作5的存在，需要将线段树可持久化

因为所有版本的线段树的根有NQ个，所以不能直接保存根的位置

我们的做法是只保存有修改的根，回答操作5时二分查找

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 500100
#define N 500000
#define INF 1e9
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int n,Q,cnt,ans,root[MAXN],mex[MAXN*40],son[MAXN*40][2];
ll sum[MAXN*40];
vector<pii>data[MAXN];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline int get(){return (read()+ans-1)%n+1;}
void save_root(int x,int T){data[x].push_back(make_pair(T,root[x]));}
void relord(int root,int l,int r){
	int mid=(l+r)>>1;
	int lmex=son[root][0]?mex[son[root][0]]:l;
	int rmex=son[root][1]?mex[son[root][1]]:mid+1;
	mex[root]=min(lmex,rmex);
	sum[root]=sum[son[root][0]]+sum[son[root][1]];
}
void newnode(int &root){
	int p=++cnt;
	son[p][0]=son[root][0];
	son[p][1]=son[root][1];
	sum[p]=sum[root];
	mex[p]=mex[root];
	root=p;
}
void insert(int l,int r,int &root,int pos){
	newnode(root);
	if(l==r){
		sum[root]+=l;
		if(sum[root]) mex[root]=INF;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) insert(l,mid,son[root][0],pos);
	else insert(mid+1,r,son[root][1],pos);
	relord(root,l,r);
}
void del(int l,int r,int &root,int pos){
	newnode(root);
	if(l==r){
		sum[root]-=l;
		if(sum[root]<0) sum[root]=0;
		if(sum[root]==0) mex[root]=l;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) del(l,mid,son[root][0],pos);
	else del(mid+1,r,son[root][1],pos);
	relord(root,l,r);
}
void merge(int l,int r,int &x,int y){
	if(x==0||y==0) {x=x+y;return;}
	if(l==r){
		sum[++cnt]=sum[x]+sum[y];
		mex[cnt]=sum[cnt]?INF:l;
		x=cnt; return;
	}
	int mid=(l+r)>>1; newnode(x);
	merge(l,mid,son[x][0],son[y][0]);
	merge(mid+1,r,son[x][1],son[y][1]);
	relord(x,l,r);
}
ll getsum(int l,int r,int root,int pos){
	if(!root||l>r) return 0;
	if(r<=pos) return sum[root];
	int mid=(l+r)>>1; ll ret(0);
	ret+=getsum(l,mid,son[root][0],pos);
	ret+=getsum(mid+1,r,son[root][1],pos);
	return ret;
}
int query(int root){
	ll now=getsum(1,N,root,1),last=0;
	while(now>=last){
		last=now+1;
		now=getsum(1,N,root,last);
	}
	printf("%d %lld\n",mex[root],last);
	return mex[root];
}
void dfs(int l,int r,int root){
	if(!root) return;
	if(l==r){
		for(int i=1;i<=sum[root]/l;++i) printf("%d ",l);
		return;
	}
	int mid=(l+r)>>1;
	dfs(l,mid,son[root][0]); 
	dfs(mid+1,r,son[root][1]);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  Q=read();  mex[0]=1;
	for(int i=1;i<=Q;++i){
		int opt=read();
		if(opt==1){
			int x=get(),v=read(); save_root(x,i);
			insert(1,N,root[x],v);
		}
		else if(opt==2){
			int x=get(),v=read(); save_root(x,i);
			del(1,N,root[x],v);
		}
		else if(opt==3){
			int x=get(),y=get(); if(x==y) continue;
			save_root(x,i);  save_root(y,i);
			merge(1,N,root[x],root[y]);  root[y]=0;
		}
		else if(opt==4){int x=get();ans=query(root[x]);}
		else{
			int x=get(),T=read();
			vector<pii>::iterator it=lower_bound(data[x].begin(),data[x].end(),make_pair(T,0));
			int temp=(it==data[x].end()?root[x]:it->second);
			ans=query(temp);
		}
	}
	for(int i=1;i<=n;++i)dfs(1,N,root[i]),puts("0");
	return 0;
}

本文标题:【日常小测】青青草原播种计划

文章作者:chty

发布时间:2017年06月26日 - 19时55分

最后更新:2018年07月25日 - 21时30分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,