https://www.luogu.org/problemnew/show/1903
用pre[i]数组记录上一次和当前i同色的位置
查询[l,r]，若pre[i]<r，则说明在[l,i)区间内没用和i同色的，则++ans
于是就可以大胆地分块
对于每一块按照pre[i]排序，再进行二分了
复杂度O(qsqrt(n)log(n)).
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using std::sort;
using std::lower_bound;
const int N=10011;
const int M=1000011;
inline int min(int a,int b){
return a<b?a:b;
}
int n,q,m,blo;
int c[N],pos[N],pre[N],b[N],last[M];
inline int find(int x,int v){
int l=(x-1)*blo+1,r=min(x*blo,n);
return lower_bound(pre+l,pre+r+1,v)-pre-l;
}
inline void reset(int x){
int l=(x-1)*blo+1,r=min(x*blo,n);
FOR(i,l,r)pre[i]=b[i];
sort(pre+l,pre+r+1);
}
inline void build(){
FOR(i,1,n){
b[i]=last[c[i]];
last[c[i]]=i;
pos[i]=(i-1)/blo+1;
}
FOR(i,1,m)reset(i);
}
inline int ask(int l,int r){
int ans=0;
if(pos[l]==pos[r]){
FOR(i,l,r)if(b[i]<l)++ans;
return ans;
}
for(register int i=l;i<=blo*pos[l];++i)if(b[i]<l)++ans;
for(register int i=blo*(pos[r]-1)+1;i<=r;++i)if(b[i]<l)++ans;
for(register int i=pos[l]+1;i<pos[r];++i)ans+=find(i,l);
return ans;
}
inline void change(int x,int v){
FOR(i,1,n)last[c[i]]=0;
c[x]=v;
FOR(i,1,n){
int t=b[i];
b[i]=last[c[i]];
if(t!=b[i])reset(pos[i]);
last[c[i]]=i;
}
}
int main(){
scanf("%d%d",&n,&q);
FOR(i,1,n)scanf("%d",c+i);
blo=int(sqrt(n));
m=n%blo?(n/blo+1):n/blo;
build();
char ch[5];int x,y;
while(q--){
scanf("%s%d%d",ch,&x,&y);
if(ch[0]=='Q')printf("%d
",ask(x,y));
else change(x,y);
}
return 0;
}
补一份带修莫队板子
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using std::swap;
using std::sort;
const int N=10011,M=300011;
int blo,times,n,m,l,r,tot,now,res;
struct qs{
int l,r,t,id;
inline bool operator<(qs A)const{
if(l/blo!=A.l/blo)return l<A.l;
if(r/blo!=A.r/blo)return r<A.r;
if(t/blo!=A.t/blo)return t<A.t;
return id<A.id;
}
}q[N];
struct cg{int p,x;}c[N];
int a[N],ans[N],hv[M];
char Q[5];
inline void add(int x){if(!hv[x])++res;++hv[x];}
inline void del(int x){--hv[x];if(!hv[x])--res;}
inline void change(int x,int i){
if(c[x].p>=q[i].l&&c[x].p<=q[i].r){
--hv[a[c[x].p]];if(!hv[a[c[x].p]])--res;
if(!hv[c[x].x])++res;++hv[c[x].x];
}
swap(c[x].x,a[c[x].p]);
}
int main(){
scanf("%d%d",&n,&m);blo=pow(n,2.00/3.00);
FOR(i,1,n)scanf("%d",a+i);
FOR(i,1,m){
scanf("%s%d%d",Q,&l,&r);
if(Q[0]=='Q')
q[++tot]=(qs){l,r,times,tot};
else c[++times]=(cg){l,r};
}
sort(q+1,q+tot+1);
l=1;r=0;now=0;
FOR(i,1,m){
while(l<q[i].l)del(a[l++]);while(q[i].l<l)add(a[--l]);
while(r<q[i].r)add(a[++r]);while(q[i].r<r)del(a[r--]);
while(now<q[i].t)change(++now,i);while(q[i].t<now)change(now--,i);
ans[q[i].id]=res;
}
FOR(i,1,tot)printf("%d
",ans[i]);
return 0;
}
线段树+bitset
#include<stdio.h>
#include<bitset>
#include<algorithm>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using std::bitset;
using std::sort;
using std::unique;
using std::lower_bound;
const int N=10011;
bitset<N>s[N<<2],ans;
int a[N];
int b[N<<2];
inline void build(int k,int l,int r){
if(l==r){
s[k][a[l]]=1;
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
s[k]=s[k<<1]|s[k<<1|1];
}
int n,m,cnt;
inline void change(int k,int l,int r,int x,int v){
if(l==r){
s[k][a[l]]=0;
s[k][a[l]=v]=1;
return;
}
int mid=(l+r)>>1;
x<=mid?change(k<<1,l,mid,x,v):change(k<<1|1,mid+1,r,x,v);
s[k]=s[k<<1]|s[k<<1|1];
}
inline void query(int k,int l,int r,int x,int y){
if(x<=l&&r<=y){
ans|=s[k];
return;
}
int mid=(l+r)>>1;
if(x<=mid) query(k<<1,l,mid,x,y);
if(mid<y) query(k<<1|1,mid+1,r,x,y);
}
struct question{
char c;
int x;
int y;
}q[N];
inline void disc_init(){
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
}
inline int read(){
char c;while(c=getchar(),c==' '||c=='
');int data=c-48;
while(c=getchar(),c>='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data;
}
int main(){
scanf("%d%d
",&n,&m);
FOR(i,1,n)b[++cnt]=a[i]=read();
scanf("
");
FOR(i,1,m){
q[i].c=getchar();
q[i].x=read();q[i].y=read();
scanf("
");
if(q[i].c=='R')b[++cnt]=q[i].y;
}
disc_init();
FOR(i,1,n)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
build(1,1,n);
FOR(i,1,m){
if(q[i].c=='Q'){
ans.reset();
query(1,1,n,q[i].x,q[i].y);
printf("%d
",ans.count());
}
else{
q[i].y=lower_bound(b+1,b+cnt+1,q[i].y)-b;
change(1,1,n,q[i].x,q[i].y);
}
}
return 0;
}