经典区间数颜色问题。
离线做法有树状数组和莫队，在线做法有主席树。
莫队做法十分暴力，直接维护每个数当前的 cnt 再在单点更新的时候更新答案即可。
树状数组做法：
对于每一个位置维护一个前缀位置 (pre)，那么询问就相当于是询问区间多少个位置的 (pre) 在 (l) 之前。
我们可以考虑离线下来然后差分，具体来说就是每次维护当前点为右端点，左端点为 1 时的值域树状数组，维护小于等于数 x 的 pre 有多少个，这个信息显然可以差分。
然后主席树做法就是在线维护，每次直接在多树上询问即可。
树状数组代码：
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
struct node{
int l,r;
int before;
int ans;
}q[1000005];
int a[1000005],n,m,c[1000005],pre[1000005],used[1000005],p[1000005];
inline int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline int lowbit(int x){return x&(-x);}
inline bool cmp(node o,node p){return o.r<p.r;}
inline void add(int x,int t){if(!x){return ;}while(x<=n){c[x]+=t;x+=lowbit(x);}return;}
inline int query(int x){int ans=0;while(x){ans+=c[x];x-=lowbit(x);}return ans;}
int main(){
n=read();
for(int i=1;i<=n;++i){a[i]=read();}
for(int i=1;i<=n;++i){
pre[i]=used[a[i]];
used[a[i]]=i;
}
m=read();
for(int i=1;i<=m;++i){
q[i].l=read();
q[i].r=read();
q[i].before=i;
}
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++) p[q[i].before] = i;
int j=1;
for(int i=1;i<=m;++i){
while(j<=q[i].r){
add(j,1);
add(pre[j],-1);
j++;
}
q[i].ans=query(q[i].r)-query(q[i].l-1);
}
for(int i=1;i<=m;++i) printf("%d
",q[p[i]].ans);
return 0;
}
莫队
#include<bits/stdc++.h>
using namespace std;
#define ri register int
#define MAXN 1001000
#define MAXA 1001000
#define MAXQ 1001000
#include <sys/mman.h>
int a[MAXN],cnt[MAXA],bnum,q,n,belong[MAXA],siz,ans1[MAXQ];
struct node{
int l,r,id;
}lin[MAXQ];
struct _io {
char* s;
_io() : s((char*)mmap(0, 1 << 25, PROT_READ, MAP_PRIVATE, fileno(stdin), 0)) {}
operator int() {
int x = 0,w=0;
while((*s)<'0') w|=(!((*s)^45)),++s;
while((*s)>='0') x=(x<<3)+(x<<1)+((*s++)&15);
return x*(w?-1:1);
}
} it;
#define read() it
template< typename T >inline void write(T x)
{
if(x>9) write(x/10);
putchar(x%10^48);
}
inline bool cmp(node a,node b)
{
return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r:a.r>b.r);
}
int main()
{
n=read();
siz=2135;
bnum=ceil((double)n/siz);
for(ri i=1;i<=n;++i)
{
belong[i]=i/siz;
}
for(ri i=1;i<=n;++i) a[i]=read();
q=read();
for(ri i=1;i<=q;++i)
{
lin[i].l=read(),lin[i].r=read();
lin[i].id=i;
}
sort(lin+1,lin+1+q,cmp);
int l=1,r=0,now=0;
for(ri i=1;i<=q;++i)
{
int ql=lin[i].l,qr=lin[i].r;
while(l<ql) now-=!--cnt[a[l++]];
while(l>ql) now+=!cnt[a[--l]]++;
while(r<qr) now+=!cnt[a[++r]]++;
while(r>qr) now-=!--cnt[a[r--]];
ans1[lin[i].id]=now;
}
for(ri i=1;i<=q;++i)
{
write(ans1[i]);
putchar('
');
}
}