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

首先，假设你会了不带修改的莫队（不会出门右拐百度）

我们来想一想莫队如何支持修改，我们把查询和修改操作离线下来，如图，将查询标为蓝色，将修改标为红色。

假设我们要查询六号查询的答案，考虑哪些修改会影响答案，肯定是在六号之前的修改，且这些修改的下标 $ind$ 在六号查询的区间 $[l,r]$ 之内，如图中 $2$ ， $4$ 号修改，要把这些修改全部做完，才能得到正确的结果。

所以，我们在每个查询中除了 $l,r,id$ ，还要记录一个 $last$ ，代表最近的修改位置，查询时，我们要把 $last$ 前面的修改全部做完，如代码。

1
2
3

struct Query{
    int l,r,id,last;//last为最近的修改位置
}q[MAXN];

同时记录每个修改操作，只用记录修改的下标 $ind$ 和修改的值 $val$ 即可。

1
2
3

struct Update{
    int ind,val;//把ind修改成val
}u[MAXN];

为了做带修莫队，我们记录一个指针 $p$ ，代表我们把 $[1,p]$ 的修改操作全部做完了，做莫队的时候，除了常规的莫队操作，还要有下面两行：

1 2	while (p<q[i].last) Upd(++p,i); while (p>q[i].last) Upd(p--,i);

如果操作做少了，那么我们调用 $Upd(++p,i)$ ，多做一次操作，如果操作做少了，我们调用 $Upd(p--,i)$ ，撤销一次操作。

那么这个撤销怎么弄呢？

很容易想到的是，我们在每个 $Update$ 结构体里面再多存一个 $flag$ ，代表当前是增加操作还是撤销操作，如果是撤销操作，那么我们删除 $u[p].val$ ，加入 $num[u[p].ind]$ ，每次操作后， $flag$ 取反，即撤销操作变成加入操作，加入操作变成撤销操作。

但是呢，这样代码量不但增加，常数也增多了，这道题你可能 $TLE$ ，考虑有没有更加简洁优美的方法替代 $flag$ 。

有！

我们每次操作之后，将 $num[u[p].ind]$ 和 $u[p].val$ 对调，我们再撤销回去的时候，就相当于将 $u[p].val$ 改成 $num[u[p].ind]$ ，非常巧妙。

实现如下，注意只有修改的下标在现在查询范围之内才会对答案造成影响：

inline void Upd(int p,int i){
    if (q[i].l<=u[p].ind&&u[p].ind<=q[i].r){
        Del(num[u[p].ind]),Add(u[p].val);//修改，先删去原有的，再加进val
    }
    swap(num[u[p].ind],u[p].val);
}

注意要加 $sort$ ，（虽然我不加 $sort$ 也卡过）

#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline 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<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
struct Query{
    int l,r,id,last;//last为最近的修改位置
}q[MAXN];
struct Update{
    int ind,val;//把ind修改成val
}u[MAXN];
int pos[MAXN],num[MAXN];
inline bool operator < (const Query &x,const Query &y){
	if(pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];
	if(pos[x.r]!=pos[y.r]) return pos[x.r]<pos[y.r];
	return x.last<y.last;
}
int cntq,cntu;
inline char gc(){
    char ch=getchar();
    while (ch!='Q'&&ch!='R') ch=getchar();
    return ch;
}
int ans,Ans[MAXN];
static int cnt[MAXN];
#define Add(x) (++cnt[x]==1)?++ans:0
#define Del(x) (--cnt[x]==0)?--ans:0
inline void Upd(int p,int i){
    if (q[i].l<=u[p].ind&&u[p].ind<=q[i].r){
        Del(num[u[p].ind]),Add(u[p].val);//修改，先删去原有的，再加进val
    }
    swap(num[u[p].ind],u[p].val);
}
inline void Print(register int x){
    if (x>=10ll) Print(x/10ll);
    putchar(x%10ll+48ll);
}
inline void print(register int x,const char ch){
    if (x<0){x=-x,putchar('-');}
    if (x==0){putchar('0');putchar(ch);return ;}
    Print(x);putchar(ch);
}
int main(){
    int n=read(),m=read();
    const int Size=pow(n,(double)0.666666666);
    for (register int i=1;i<=n;++i){
        num[i]=read();
    }
    for (register int i=1;i<=m;++i){
        char opr=gc();
        if (opr=='Q') q[++cntq]=Query{read(),read(),cntq,cntu};
        else u[++cntu]=Update{read(),read()};
    }
    for (register int i=1;i<=n;++i){
        pos[i]=(i-1)/Size+1;
	}
    sort(q+1,q+1+cntq);
    register int l=1,r=0;
    register int p=0;//修改的操作
    for (register int i=1;i<=m;++i){
        while (l<q[i].l) Del(num[l++]);
        while (l>q[i].l) Add(num[--l]);
        while (r<q[i].r) Add(num[++r]);
        while (r>q[i].r) Del(num[r--]);
        while (p<q[i].last) Upd(++p,i);
        while (p>q[i].last) Upd(p--,i);
        Ans[q[i].id]=ans;
    }
    for (register int i=1;i<=cntq;++i){
        print(Ans[i],'\n');
    }
}