P1903 [国家集训队] 数颜色 / 维护队列

好像之前位置的写法是错误的。

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;
using a4=std::array<int,4>;

char opt;
int n,m,tot=1,a[(int)2e5+9],fk,belong[(int)2e5+9],l=1,r,cnt[(int)1e6+9],ans,now=1,res[(int)2e5+9];
struct{
    int pos,val;
}modify[(int)2e5+9];



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    vector<a4> q;
    for(int i=1,x,y;i<=m;++i){
        cin>>opt>>x>>y;
        if(opt=='Q'){
            q.push_back({x,y,tot,i});
        }else {
            modify[++tot]={x,y};
        }
    }
    fk=ceil(pow(n,2.0/3.0)*pow(tot,1.0/3.0)/pow(m,1.0/3.0));
    for(int i=1;i<=n;++i)belong[i]=(i-1)/fk+1;
    sort(all(q),[](const a4 &aa,const a4 &bb){
        if(belong[aa[0]]!=belong[bb[0]])return belong[aa[0]]<belong[bb[0]];
        if(belong[aa[1]]!=belong[bb[1]])return belong[aa[0]]&1?aa[1]<bb[1]:aa[1]>bb[1];
        return aa[2]<bb[2];
    });
    
    for(auto [aa,bb,cc,dd]:q){
        while(l>aa)ans+=(++cnt[a[--l]]==1);
        while(r<bb)ans+=(++cnt[a[++r]]==1);
        while(l<aa)ans-=(--cnt[a[l++]]==0);
        while(r>bb)ans-=(--cnt[a[r--]]==0);
        while(now<cc){
            now+=1;
            if(modify[now].pos>=aa&&modify[now].pos<=bb){ans-=(--cnt[a[modify[now].pos]]==0);ans+=(++cnt[modify[now].val]==1);}
            swap(modify[now].val,a[modify[now].pos]);
        }
        while(now>cc){
            if(modify[now].pos>=aa&&modify[now].pos<=bb){ans-=(--cnt[a[modify[now].pos]]==0);ans+=(++cnt[modify[now].val]==1);}
            swap(modify[now].val,a[modify[now].pos]);
            now-=1;
        }
        res[dd]=ans;
    }

    for(int i=1;i<=m;++i)if(res[i])cout<<res[i]<<"\n";
    return 0;
}