一、题目
其实是一道带修莫队的模板题啊。
二、解法
普通莫对其实是一个二维的信息 ((l,r))，既然要支持修改，我们添加一个信息表示这个询问用到的修改是 ([1,t])，那么我们可以用一个三维信息来表示一个询问 ((l,r,t))
排序的方法是这样的：先判断 (l) 在不在一个块内，不在一个块内就直接排；再判断 (r) 在不在一个块内，不在一个块内就直接排；最后按 (t) 从小到大排序。排完序之后直接按普通莫队的做法做就行，实现代码如下：
bool operator < (const node &b) const
{
if(pos[l]!=pos[b.l]) return l<b.l;
if(pos[r]!=pos[b.r]) return r<b.r;
return t<b.t;
}
本文的重点是证明待修莫对的时间复杂度，时间消耗主要分成三个部分，设块长为 (a)：
- (t) 轴的移动时间复杂度，因为 ((l,r)) 的组合只有 (frac{n^2}{a^2}) 种，每一种的时间消耗为 (t)，总时间复杂度 (O(frac{n^2}{a^2}t))
- 如果 (l,r) 所在块相同那么 (l,r) 的移动复杂度为 (O(na))，可以看做每一个询问都在块里面乱动。
- (l) 从一个块到另一个块时 (r) 移动的时间复杂度为 (O(frac{n^2}{a}))，单次是 (O(n)) 的乘上的块的个数。
(a) 一般取 (O(n^{frac{5}{3}}))，我习惯于把块长设为定值。还有这道板题有一个细节，就是我们要在修改处记录修改之前的权值，这样就方便回退了。
#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 200005;
const int sq = 2412;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,ans,ln,l,r,t,res[M],cnt[5*M];
int a[M],b[M],c[M],d[M],pos[M];char s[M];
struct node
{
int l,r,t,id;
bool operator < (const node &b) const
{
if(pos[l]!=pos[b.l]) return l<b.l;
if(pos[r]!=pos[b.r]) return r<b.r;
return t<b.t;
}
}q[M];
void add(int x)
{
if(cnt[x]==0) ans++;
cnt[x]++;
}
void del(int x)
{
cnt[x]--;
if(cnt[x]==0) ans--;
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=n;i++)
pos[i]=(i-1)/sq+1;
for(int i=1;i<=m;i++)
{
scanf("%s",s);
int l=read(),r=read();
if(s[0]=='Q') q[++ln]=node{l,r,k,ln};
else k++,b[k]=l,c[k]=r;
}
sort(q+1,q+1+ln);
l=1;r=0;t=0;
for(int i=1;i<=ln;i++)
{
int L=q[i].l,R=q[i].r,T=q[i].t;
while(L<l) add(a[--l]);
while(L>l) del(a[l++]);
while(R>r) add(a[++r]);
while(R<r) del(a[r--]);
while(t<T)//增加t这个修改
{
t++;
if(l<=b[t] && b[t]<=r) del(a[b[t]]);
d[t]=a[b[t]];//记录下修改之前的信息
a[b[t]]=c[t];
if(l<=b[t] && b[t]<=r) add(a[b[t]]);
}
while(t>T)//回撤t这个修改
{
if(l<=b[t] && b[t]<=r) del(a[b[t]]);
a[b[t]]=d[t];
if(l<=b[t] && b[t]<=r) add(a[b[t]]);
t--;
}
res[q[i].id]=ans;
}
for(int i=1;i<=ln;i++)
printf("%d
",res[i]);
}