传送门:

Codeforces

洛谷


Solution

考虑用带修莫队来解决这题。

我们很显然要先对出现的权值离散化,然后我们对区间排序,依次处理。

现在问题是要怎么求出\rm mex(注意是每个数字出现次数\rm mex,而不是这个区间的\rm mex)。我们考虑用一个桶存下来每个数字出现次数的出现次数,然后每次统计完区间内数字出现次数的出现次数之后,直接暴力枚举去求出\rm mex就好了。

我们考虑这样做的时间复杂度。假设我们的\rm mexx,那么\sum_{i=1}^ni \leqslant n,所以最坏情况下我们求解答案的复杂度大约是n^{0.55}n^{0.56}之间,而带修莫队的复杂度是n^{\frac{5}{3}},是不会超过主复杂度的。

Code

/*Program from Luvwgyx*/
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int maxn=2e5+10;
struct Query2{int p,x;}q2[maxn];
struct Query1{int l,r,t,pos;}q1[maxn];
int n,m,B,tot,tot1,tot2,a[maxn],cnt[maxn],f[maxn],ans[maxn],lst[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
bool cmp(Query1 x,Query1 y){return x.l/B==y.l/B?(x.r/B==y.r/B?x.t<y.t:x.r/B<y.r/B):x.l/B<y.l/B;}
void add(int x){f[cnt[x]]--;cnt[x]++;f[cnt[x]]++;}
void del(int x){f[cnt[x]]--;cnt[x]--;f[cnt[x]]++;}
void change(int x,int tim){
    if(q1[x].l<=q2[tim].p&&q2[tim].p<=q1[x].r){
        del(a[q2[tim].p]);
        add(q2[tim].x);
    }swap(a[q2[tim].p],q2[tim].x);
}
int main(){
    n=read();m=read();B=pow(n,0.666666);
    for(int i=1;i<=n;i++)a[i]=read(),lst[++tot]=a[i];
    for(int i=1;i<=m;i++){
        int opt=read(),x=read(),y=read();
        if(opt==1)q1[++tot1]=(Query1){x,y,tot2,tot1};
        else q2[++tot2]=(Query2){x,y},lst[++tot]=q2[tot2].x;
    }sort(q1+1,q1+tot1+1,cmp);int l=1,r=0,now=0;
    sort(lst+1,lst+tot+1);tot=unique(lst+1,lst+tot+1)-lst-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(lst+1,lst+tot+1,a[i])-lst;
    for(int i=1;i<=tot2;i++)q2[i].x=lower_bound(lst+1,lst+tot+1,q2[i].x)-lst;
    for(int i=1;i<=tot1;i++){
        while(l>q1[i].l)add(a[--l]);
        while(r<q1[i].r)add(a[++r]);
        while(l<q1[i].l)del(a[l++]);
        while(r>q1[i].r)del(a[r--]);
        while(now<q1[i].t)change(i,++now);
        while(now>q1[i].t)change(i,now--);
        for(int j=1;j<=n;j++)if(!f[j]){ans[q1[i].pos]=j;break;}
    }for(int i=1;i<=tot1;i++)write(ans[i]);
    return 0;
}

发表评论