给一个序列 \(a\),两个操作:
- 1、给 \(l,r\) ,设 \(a_l,\dots,a_r\) 这些数集中每个数 \(v\) 的出现次数是 \(c_v\),要求 \(\mathrm{mex} (c_i)\) .
- 2、单点修改
\(1\leq n,q\leq 10^5\),时限4s
这种一眼看过去很难维护的信息,一般就先找找性质。
首先注意到关键性质:要求的是出现次数的mex,如果mex是 \(m\) 的话,意味着存在出现 \(1,\dots,m-1\) 次的数字,则区间长度至少是 \(1+2+\dots+(m-1)=O(m^2)\),所以mex至多是 \(O(\sqrt n)\) 的。
如果添加一个数字\(v\),会让 \(cnt_v\to cnt_v+1\),同时假设 \(sz_i\) 表示出现 \(i\) 次的数字个数,则会让原本的 sz[cnt[v]]--
,以及 sz[cnt[v]+1]++
,删除操作同理,对 cnt,sz
的修改都可以 \(O(1)\) 完成。
那如何维护mex呢?一开始我犯了个错误就是企图在莫队里动态维护mex,明明一读完题就看出来 \(O(\sqrt n)\) 的性质了…
直接用带修莫队维护 cnt,sz
的信息,对于每个询问,\(O(\sqrt n)\) 地暴力跑mex就行了…这样的复杂度是 \(O(q\sqrt n+n^{5/3})\) 的,瓶颈是在带修莫队上面。
写这道题的时候主要犯了两个错误:
- 一是想的时候没有去想把求解mex和莫队分开,想破了脑子不知道怎么快速更新mex的信息,最后看了眼题解马上就懂了。
- 二是写代码的时候,居然把离散化写错了…调试调了半天…
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=1e5+5;
struct Query{int l,r,idx,times;}Q[N];
struct Modify{int p,x;}M[N];
int n,q,cq,cm;
int cnt[N<<1],sz[N],a[N],b[N<<1],tot,ans[N];
int bl[N],S;
void add(int v){
sz[cnt[v]]--;
cnt[v]++;
sz[cnt[v]]++;
}
void del(int v){
sz[cnt[v]]--;
cnt[v]--;
sz[cnt[v]]++;
}
void modify(int ql,int qr,int t){
int p=M[t].p;
if(ql<=p&&p<=qr)del(a[p]);
swap(a[p],M[t].x);
if(ql<=p&&p<=qr)add(a[p]);
}
int get_ans(){
rep(i,1,N-5)if(!sz[i])return i;
return -1;
}
int main(){
fastio;
//prework
cin>>n>>q;
rep(i,1,n)cin>>a[i],b[++tot]=a[i];
rep(i,1,q){
int op,l,r,p,x;
cin>>op;
if(op==1){
cq++;
cin>>Q[cq].l>>Q[cq].r;
Q[cq].idx=cq;
Q[cq].times=cm;
}else{
cm++;
cin>>M[cm].p>>M[cm].x;
b[++tot]=M[cm].x;
}
}
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-(b+1);
auto get=[&](int v)->int{
return lower_bound(b+1,b+tot+1,v)-b;
};
rep(i,1,n)a[i]=get(a[i]);
rep(i,1,cm)M[i].x=get(M[i].x);
//block
S=pow(n,2.0/3.0)+1;
rep(i,1,n)bl[i]=(i-1)/S+1;
sort(Q+1,Q+cq+1,[&](Query a,Query b){
if(bl[a.l]!=bl[b.l])return a.l<b.l;
if(bl[a.r]!=bl[b.r])return a.r<b.r;
return a.times<b.times;
});
//Mo's algorithm
int l=Q[1].l,r=Q[1].l-1,now=0;
rep(i,1,cq){
int ql=Q[i].l,qr=Q[i].r,qt=Q[i].times;
while(l>ql)add(a[--l]);
while(r<qr)add(a[++r]);
while(l<ql)del(a[l++]);
while(r>qr)del(a[r--]);
while(now<qt)modify(ql,qr,++now);
while(now>qt)modify(ql,qr,now--);
ans[Q[i].idx]=get_ans();
}
rep(i,1,cq)cout<<ans[i]<<endl;
return 0;
}
标签:cnt,cm,rep,tot,mex,Machine,CF940F,cq,Mex
From: https://www.cnblogs.com/yoshinow2001/p/18171630