带修莫队
cpp
namespace MoDynamic{
// 带修莫队
struct Node{
int id,l,r,t;
};
// be块编号，[L,R]块边界
vector<int> be,L,R;
// block块大小, tot块数量
int block,tot;
vector<Node> que; // 询问
vector<array<int,2>> c; // 带修辅助数组
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 init(int n){
block=pow(n,2.0/3);
tot=(n+block-1)/block;
be.assign(n+1,0);
L.assign(tot+1,0);
R.assign(tot+1,0);
que.clear();
c={{0,0}};
for(int i=1;i<=tot;i++){
L[i]=block*(i-1)+1,R[i]=min(block*i,n);
for(int j=L[i];j<=R[i];j++)be[j]=i;
}
}
void add_update(int x,int y){
c.push_back({x,y});
}
void add_query(int l,int r){
int id=que.size(),t=c.size()-1;
que.push_back({id,l,r,t});
}
}
using namespace MoDynamic;
void solve(){
int n,m;
cin>>n>>m;
vector<int> w(n+1);
int mx=0;
for(int i=1;i<=n;i++)cin>>w[i],mx=max(mx,w[i]);
vector<int> cnt(mx+1);
init(n);
for(int i=0;i<m;i++){
char op;
int x,y;
cin>>op>>x>>y;
if(op=='Q')add_query(x,y);
else add_update(x,y);
}
auto work=[&](){
sort(que.begin(),que.end(),cmp);
vector<int> ans(que.size());
int res=0;
auto add=[&](int x){
if(!(cnt[x]++))res++;
};
auto del=[&](int x){
if(!(--cnt[x]))res--;
};
auto change=[&](int t,int l,int r){
int pos=c[t][0];
if(l<=pos&&r>=pos)del(w[pos]),add(c[t][1]);
swap(w[pos],c[t][1]);
};
int l=1,r=0,t=0;
for(auto [id,ql,qr,qt]:que){
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)change(++t,ql,qr);
while(t>qt)change(t--,ql,qr);
ans[id]=res;
}
return ans;
};
for(auto &x:work())cout<<x<<"\n";
}