- http://www.lydsy.com/JudgeOnline/problem.php?id=2120
- http://www.lydsy.com/JudgeOnline/problem.php?id=2453
- https://www.luogu.com.cn/problem/P1903
没想到吧,我大莫队也能修改!
对于每次询问,按左端点所在块为第一关键字,右端点所在块为第二关键字,影响它的上一个询问为第三关键字进行排序。
在每次处理询问时,同时对时间戳进行移动,将修改的贡献算出来。
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#include <emmintrin.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
const int N=133333+10;
int n,m;
int co[N],len;
struct query {
int l,r,pre,id;
} q[N];
struct change {
int x,y;
} c[N];
int qn,cn;
char opt;
inline int read() {
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
return x*f;
}
bool cmp(query _,query __) {
if(_.l/len!=__.l/len)
return _.l/len<__.l/len;
if(_.r/len!=__.r/len)
return _.r/len<__.r/len;
return _.pre<__.pre;
}
int ans,L=1,R,now,cnt[1000010],tans[N];
void add(int x) {
if(++cnt[x]==1)
ans++;
//printf("use add %d
",ans);
}
void del(int x) {
if(--cnt[x]==0)
ans--;
//printf("use del %d
",ans);
}
void work(int t,int i) {
if(c[t].x<=q[i].r&&c[t].x>=q[i].l) {
if(--cnt[co[c[t].x]]==0)
ans--;
if(++cnt[c[t].y]==1)
ans++;
}
swap(co[c[t].x],c[t].y);
//printf("%d use change %d: %d to %d,ans change to %d
",i,t,c[t].x,c[t].y,ans);
}
int main() {
n=read(),m=read();
len=pow(n,0.667);
//build();
for(int i=1;i<=n;i++)
co[i]=read();
for(int i=1;i<=m;i++) {
cin>>opt;
if(opt=='Q') {
++qn;
q[qn].l=read(),q[qn].r=read();
q[qn].pre=cn,q[qn].id=qn;
//printf("%d %d
",q[qn].l,q[qn].r);
}
else if(opt=='R') {
++cn;
c[cn].x=read(),c[cn].y=read();
}
}
//printf("%d
",q[1].id);
sort(q+1,q+qn+1,cmp);
//printf("%d
",q[1].id);
for(int i=1;i<=qn;i++) {
//printf("%d
",q[i].id);
while(q[i].l<L)ans+=!cnt[co[--L]]++;
while(q[i].l>L)ans-=!--cnt[co[L++]];
while(q[i].r>R)ans+=!cnt[co[++R]]++;
while(q[i].r<R)ans-=!--cnt[co[R--]];
while(now<q[i].pre) work(++now,i);
while(now>q[i].pre) work(now--,i);
tans[q[i].id]=ans;
//puts("");
}
for(int i=1;i<=qn;i++)
printf("%d
",tans[i]);
return 0;
}