数颜色/维护队列（带修莫队）

数颜色/维护队列

写完这题差不多直接1A？（第一次没吸氧，T了）

题意：

1. 询问：求区间 $[l,r]$[l,r]之间有多少种不同的数字
2. 修改：修改某个位置的数字
3. 不强制在线

思路：（带修莫队板子）

1. 基本与普通莫队一样，仅仅额外加上了时间这个维度（其实看代码更好懂），甚至按奇偶排序的小技巧也很好用！
2. 分块的大小也有讲究（当然也可以采用其他玄学分块）：
   设分块大小为 $a$a，莫队算法时间复杂度主要为 $t$t轴移动，同 $r$r块 $l,r$l,r移动， $l$l块间的 $r$r移动三个部分:
   1. $t$t轴移动的复杂度为 $O\left(\frac{n^{2}t}{a^2}\right)$O(a2n2t​)，
   2. 同 $r$r块 $l,r$l,r移动复杂度为 $O\left(na\right)$O(na)，
   3. $l$l块间的 $r$r移动复杂度为 $O\left(\frac{n^2}{a}\right)$O(an2​)
   4. 因此三个函数 $max$max的最小值当 $a$a为 $\sqrt[3]{nt}$3nt ​取得，为 $O\left(\sqrt[3]{n^{4}t}\right)$O(3n4t ​)
3. 然后就没什么特别的啦！

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1.4e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

char s[2];
int N, M, cntp, cntq, len, num;
int c[maxn], cnt[maxn*10], ans[maxn];

struct P{
    int pos, pre, to;
}p[maxn];

struct Q{
    int l, r, t, id;
    friend bool operator < (const Q &a, const Q &b) {
        if((a.l-1)/len!=(b.l-1)/len) return a.l<b.l;
        if((a.r-1)/len!=(b.r-1)/len) { //仍然可以采用奇偶排序
            if((a.l-1)/len%2) return a.r>b.r;
            return a.r<b.r;
        }
        if((a.r-1)/len%2) return a.t>b.t;
        return a.t<b.t;
    }
}q[maxn];

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    N=read(), M=read();
    for(int i=1; i<=N; ++i) c[i]=read();
    for(int i=1; i<=M; ++i) {
        scanf("%s", s);
        int l=read(), r=read();
        if(s[0]=='Q') ++cntq, q[cntq]=(Q){l,r,cntp,cntq};
        else {
            ++cntp; p[cntp].pos=l;
            p[cntp].pre=c[p[cntp].pos];
            p[cntp].to=c[p[cntp].pos]=r;
        }
    }
    len=ceil(pow(1.*N*cntq,1./3));
    sort(q+1,q+1+cntq);
    for(int i=cntp; i; --i) c[p[i].pos]=p[i].pre; //从后往前，改回最初的数组
    int l=1, r=0, t=0;
    for(int i=1; i<=cntq; ++i) {
        while(l<q[i].l) num-=!(--cnt[c[l++]]);
        while(l>q[i].l) num+=!(cnt[c[--l]]++);
        while(r<q[i].r) num+=!(cnt[c[++r]]++);
        while(r>q[i].r) num-=!(--cnt[c[r--]]); //下面两个t的移动就是额外的
        while(t<q[i].t) {
            ++t;
            if(p[t].pos>=l&&p[t].pos<=r) num-=!(--cnt[c[p[t].pos]]);
            c[p[t].pos]=p[t].to;
            if(p[t].pos>=l&&p[t].pos<=r) num+=!(cnt[c[p[t].pos]]++);
        }
        while(t>q[i].t) {
            if(p[t].pos>=l&&p[t].pos<=r) num-=!(--cnt[c[p[t].pos]]);
            c[p[t].pos]=p[t].pre;
            if(p[t].pos>=l&&p[t].pos<=r) num+=!(cnt[c[p[t].pos]]++);
            --t;
        }
        ans[q[i].id]=num;
    }
    for(int i=1; i<=cntq; ++i) printf("%d\n", ans[i]);
}