链接:lg1972
题解
- 裸的莫队，板子套上搞一搞
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
using namespace std;
const int N=5e5+7;
const int M=1e6+7;
template <typename T>inline void read(T &x){
char c;int sign=1;x=0;
do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
x*=sign;
}
int col[N],f[M],pos[N],n,m;
ll ans;
struct node{
int l,r,id,ans;
}q[N];
inline int cmp_id(node a,node b){return a.id<b.id;}
inline int cmp_pos(node a,node b){return pos[a.l]==pos[b.l]?((pos[a.l]&1)?a.r<b.r:a.r>b.r):pos[a.l]<pos[b.l];}
inline void modify1(int p,ll &ans){if(++f[col[p]]==1)ans++;}
inline void modify2(int p,ll &ans){if(--f[col[p]]==0)ans--;}
inline void init(){
read(n);
rep(i,1,n)read(col[i]);
int x=sqrt(n);
rep(i,1,n)pos[i]=(i-1)/x+1;
read(m);
rep(i,1,m){
read(q[i].l);
read(q[i].r);
q[i].id=i;
}
sort(q+1,q+m+1,cmp_pos);
}
inline void solve(){
int l=1,r=0;ans=0;
rep(i,1,m){
if(r<q[i].r){
for(r=r+1;r<q[i].r;++r)modify1(r,ans);
modify1(r,ans);
}
if(q[i].l<l){
for(l=l-1;l>q[i].l;--l)modify1(l,ans);
modify1(l,ans);
}
if(r>q[i].r)for(;r>q[i].r;--r)modify2(r,ans);
if(q[i].l>l)for(;q[i].l>l;++l)modify2(l,ans);
q[i].ans=ans;
}
sort(q+1,q+m+1,cmp_id);
rep(i,1,m)printf("%d\n",q[i].ans);
}
int main(){
init();
solve();
return 0;
}