数颜色 HYSBZ - 2120

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
int ans[maxn],cnt[maxn * 100],Ans = 0;
int a[maxn],belong[maxn];
struct xx{
    int l,r,id,time;
}Q[maxn];
struct change{
    int pos,val;
}cge[maxn];
int n,m;
bool cmp(xx A,xx B){
    if(belong[A.l] != belong[B.l])
        return belong[A.l] < belong[B.l];
    if(belong[A.r] != belong[B.r])
        return belong[A.r] < belong[B.r];
    return A.time < B.time;
}
void add(int x){
    if(!cnt[a[x]])
        ++ Ans;
    ++ cnt[a[x]];
}
void del(int x){
    if(cnt[a[x]] == 1)
        -- Ans;
    -- cnt[a[x]];
}
//到第i次询问， 
void update(int i,int _time){
    if(cge[_time].pos >= Q[i].l && cge[_time].pos <= Q[i].r)
        del(cge[_time].pos);
    swap(cge[_time].val,a[cge[_time].pos]);
    if(cge[_time].pos >= Q[i].l && cge[_time].pos <= Q[i].r)
        add(cge[_time].pos);
}
int main() {
    int n ,m ;
    cin>>n>>m;
    int block = sqrt(n);
    for(int i = 1;i <= n;++ i){
        cin>>a[i];
        belong[i] = (i - 1) / block + 1;
    }
    int tmp = 0,pq = 0;
    for(int i = 1;i <= m;++ i){
        char op; 
        scanf(" %c",&op);
        //如果是查询 
        if(op == 'Q')
        {
            //记录查询的 
            cin>>Q[++ pq].l;
            cin>>Q[pq].r ;
            Q[pq].id = pq;   
            //时间点  ，在第几次更新之前 
            Q[pq].time = tmp;
        }
        //如果是更新的话 
        else 
        {
            //记录更新 
            cin>>cge[++ tmp].pos;
            cin>>cge[tmp].val;
        }
    }
    sort(Q + 1,Q + 1 + pq,cmp);
    int L = 1,R = 0,_time = 0;
    for(int i = 1;i <= pq;++ i){
        while(L < Q[i].l) 
            del(L ++);
        while(L > Q[i].l) 
            add(-- L);
        while(R < Q[i].r) 
            add(++ R);
        while(R > Q[i].r) 
            del(R --);  
        while(_time > Q[i].time) 
            update(i,_time --);
        while(_time < Q[i].time) 
            update(i,++ _time);
        ans[Q[i].id] = Ans;
    }
    for(int i = 1;i <= pq;++ i)
        printf("%d\n",ans[i]);
    return 0;
}

数颜色 HYSBZ - 2120

原文：https://www.cnblogs.com/QingyuYYYYY/p/12380682.html