D. MEX maximizing
题意
给出一个空的数组
每次向里加入一个数yi共加入q次(q<4e5)
你可以通过向数组中任意数字+x或-x任意次使得该数列中的MEX的值尽可能的大
每次加入一个数后询问该数组的mex
对于数组[0,0,1,0,2]，MEX = 3，因为数字0、1和2在数组中表示，而3是数组中未表示的最小非负整数;
题解
不难发现+x -x的性质实际上让新加入的数yi等效转化成加入一个yi%x，统计cnt[yi%x]++;
那么对于这个数组的MEX实际就是求得从0到x-1中cnt[i]最少的数 那么MEX=最少的这个数i+x*cnt[i]
此处用线段树维护0到x-1内cnt[i]的最小值
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
|
using namespace std;
typedef long long ll;
const int maxn=(int)4e5+5;
int num[(int)4e5+5];
struct Tree{
int L,R;
int minn;
int minn_num;
}tree[maxn<<2];
inline void push_up(int i){
tree[i].minn=min(tree[i<<1].minn,tree[i<<1|1].minn);
if(tree[i<<1].minn==tree[i<<1|1].minn){
tree[i].minn_num=min(tree[i<<1].minn_num,tree[i<<1|1].minn_num);
}
else if(tree[i].minn==tree[i<<1].minn){
tree[i].minn_num=tree[i<<1].minn_num;
}
else tree[i].minn_num=tree[i<<1|1].minn_num;
return ;
}
void build(int L,int R,int i){
tree[i].L=L;tree[i].R=R;
if(L==R){
tree[i].minn=0;
tree[i].minn_num=L;
return ;
}
int mid=(L+R)>>1;
build(L,mid,i<<1);
build(mid+1,R,i<<1|1);
push_up(i);
return ;
}
void updata(int dis,int i){
if(tree[i].L==tree[i].R){
tree[i].minn++;
///cout<<tree[i].minn_num<<" "<<tree[i].minn<<endl;
return ;
}
if(dis<=tree[i<<1].R)updata(dis,i<<1);
else if(dis>=tree[i<<1|1].L)updata(dis,i<<1|1);
push_up(i);return;
}
int main() {
int q,x;cin>>q>>x;
build(0,x-1,1);
for(int i=0;i<q;i++){
int c;cin>>c;
num[c%x]++;
updata(c%x,1);
int ans=tree[1].minn_num;
//cout<<ans<<endl;
cout<<ans+x*num[ans]<<endl;
}
}
|
但可以用更简单的方法
1
2
3
4
5
6
7
8
9
10
| int now=0;
for(int i=0;i<q;i++){
int c;cin>>c;
cnt[c%x]++;
while(cnt[now%x]){
cnt[now%x]--
now++;
}
cout<<now<<" ";
}
|