Codeforces - 940F Machine Learning（带修莫队）

传送门：Codeforces - 940F

思路分析

模板题

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (int)(x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int N = 1e6+10;

int a[N],bel[N],sum[N],vis[N];


struct node{
    int l,r,id,t;
    
    bool friend operator <(node x,node y){
        if(bel[x.l] != bel[y.l]) return bel[x.l]<bel[y.l];
        if(bel[x.r] != bel[y.r]) return bel[x.r]<bel[y.r];
        return x.t<y.t;
    }
    
}q[N];

struct Change{
    int x,y;
}c[N];


vector<int>lisan;

int getid(int x){
    return lower_bound(all(lisan),x) - lisan.begin()+1;
}

int L,R,K,ans[N];

void add(int x){
    --vis[sum[x]];
    ++sum[x];
    ++vis[sum[x]];
}

void del(int x){
    --vis[sum[x]];
    --sum[x];
    ++vis[sum[x]];
}

void modify(int p){
    if(L<=c[p].x && c[p].x<=R) del(a[c[p].x]) , add(c[p].y);
    swap(c[p].y,a[c[p].x]);
}

signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,m;
    read(n,m);
    int sq = pow(n,2.0/3);
    for(int i=1;i<=n;i++) {
        read(a[i]);
        lisan.pb(a[i]);
        bel[i] = i/sq;
    }
    
    int qcnt = 0,ccnt = 0;
    for(int i=1;i<=m;i++){
        int op,l,r;
        read(op,l,r);
        if(op == 1){
            qcnt++;
            q[qcnt] = {l,r,qcnt,ccnt};
        }else{
            ccnt++;
            c[ccnt] = {l,r};
            lisan.pb(r);
        }
    }
    sort(all(lisan));
    lisan.erase(unique(all(lisan)),lisan.end());
    for(int i=1;i<=n;i++) a[i] = getid(a[i]);
    for(int i=1;i<=ccnt;i++) c[i].y = getid(c[i].y);
    
    sort(q+1,q+1+qcnt);
    L = 1,R = 0,K = 0;
    for(int i=1;i<=qcnt;i++){
        while(L<q[i].l) del(a[L++]);
        while(R<q[i].r) add(a[++R]);
        while(L>q[i].l) add(a[--L]);
        while(R>q[i].r) del(a[R--]);
        while(K<q[i].t) modify(++K);
        while(K>q[i].t) modify(K--);
        int now = 1;
        while(vis[now]) now++;
        ans[q[i].id] = now;
    }
    for(int i=1;i<=qcnt;i++) printf("%d\n",ans[i]);
    





    return 0;
}