P1903 [国家集训队] 数颜色 / 维护队列(带修莫队)
题意：
原来的基础上，加上修改某个数的操作
思路：
- 二关键字变三关键字
- 首先按l的块编号排序，再按r的块编号排序，最后按修改版本t排序
- 对于l指针,块内移动为 $ B $,总次数为 $ mB $,块间移动为 $ 2 \cdot B \cdot \frac{n}{B}=2n $,总复杂度为 $ O(mB+n) $
- 对于r指针,块内移动为 $ mB $,块间移动为 $ \frac{n^2}{B} $
- 对于t指针，移动次数为 $ \frac{n^2}{B^2}t $
- dalao证明 $ B= \sqrt[3] {nt} $ 最优
- 块长取 $ n^{\frac{2}{3}} 比 \sqrt n $ 更优，总复杂度为 $ O(n^{\frac{5}{3}}) $
- 修改操作优化，将原数组的数与修改数交换即可
cpp
struct Node{
int id,l,r,t;
};
int cnt[N],w[M];
int be[M],L[M],R[M],tot,block,res;
bool cmp(Node x,Node y){
return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:((be[x.r]^be[y.r]?be[x.r]<be[y.r]:x.t<y.t));
}
void add(int x){
if(!(cnt[x]++))res++;
}
void del(int x){
if(!(--cnt[x]))res--;
}
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
vector<Node> q;
vector<array<int,2>> c={{0,0}};
int que=0;
for(int i=0;i<m;i++){
char op;
int x,y;
cin>>op>>x>>y;
if(op=='Q'){
q.push_back({que++,x,y,c.size()-1});
}
else{
c.push_back({x,y});
}
}
vector<int> ans(que);
block=pow(n,2.0/3.0),tot=(n+block-1)/block;
for(int i=1;i<=tot;i++){
int l=(i-1)*block+1,r=min(i*block,n);
for(int j=l;j<=r;j++)be[j]=i;
}
sort(q.begin(),q.end(),cmp);
for(int i=0,l=1,r=0,t=0;i<q.size();i++){
auto [id,ql,qr,qt]=q[i];
while(r<qr)add(w[++r]);
while(r>qr)del(w[r--]);
while(l<ql)del(w[l++]);
while(l>ql)add(w[--l]);
while(t<qt){
t++;
if(ql<=c[t][0]&&qr>=c[t][0])del(w[c[t][0]]),add(c[t][1]);
swap(w[c[t][0]],c[t][1]);
}
while(t>qt){
if(ql<=c[t][0]&&qr>=c[t][0])del(w[c[t][0]]),add(c[t][1]);
swap(w[c[t][0]],c[t][1]);
t--;
}
ans[id]=res;
}
for(auto it:ans)cout<<it<<"\n";
}