1
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct node{
int l, r, val;
node *ln, *rn;
node(int _l, int _r, int _v = 0, node* _ln = nullptr, node* _rn = nullptr){
val = _v, l = _l, r = _r;
ln = _ln, rn = _rn;
return;
}
~node(){
if(ln != nullptr) delete ln;
if(rn != nullptr) delete rn;
return;
}
void Update(){
val = 0;
if(ln != nullptr) val += ln->val;
if(rn != nullptr) val += rn->val;
return;
}
};
node* Cp(node* a){return new node(a->l, a->r, a->val, a->ln, a->rn);}
node* Build(int l, int r){
if(l == r) return new node(l, r);
int md = (l+r)>>1;
return new node(l, r, 0, Build(l, md), Build(md+1, r));
}
void Update(node* nd, int p, int v){
if(nd->l == nd->r and nd->l == p){nd->val = v; return;}
int md = (nd->l+nd->r)>>1;
if(p<=md) Update(nd->ln, p, v);
else Update(nd->rn, p, v);
nd->Update();
return;
}
node* CUpdate(node* nd, int p, int v){
nd = Cp(nd);
if(nd->l == nd->r and nd->l == p){nd->val = v; return nd;}
int md = (nd->l+nd->r)>>1;
if(p<=md) nd->ln = CUpdate(nd->ln, p, v);
else nd->rn = CUpdate(nd->rn, p, v);
nd->Update();
return nd;
}
int Query(node* nd, int l, int r){
int ret = 0;
if(nd->l == l and nd->r == r) return nd->val;
int md = (nd->l+nd->r)>>1;
if(r<=md) return Query(nd->ln, l, r);
else if(l <= md) return Query(nd->ln, l, md) + Query(nd->rn, md+1, r);
else return Query(nd->rn, l, r);
}
void Print(node* nd){
if(nd->l == nd->r){ printf("%d ", nd->val); return; }
Print(nd->ln);
Print(nd->rn);
return;
}
int arr[30000];
int nxt[30000];
node* nd[30000];
int main(){
int n; scanf("%d", &n);
for(int lx = 0;lx < n;lx++) scanf("%d", arr+lx);
map<int,int> poi, ptr;
for(int lx = 0;lx < n;lx++) nxt[lx] = n;
for(int lx = 0;lx < n;lx++){
if(ptr.count(arr[lx]))
nxt[ptr[arr[lx]]] = lx;
ptr[arr[lx]] = lx;
if(poi.count(arr[lx]) == 0)
poi[arr[lx]] = poi.size();
arr[lx] = poi[arr[lx]];
}
nd[0] = Build(0, n-1);
bool vis[30000] = {0};
for(int lx = 0;lx < n;lx++){
if(vis[arr[lx]]) continue;
vis[arr[lx]] = 1;
Update(nd[0], lx, 1);
}
for(int lx = 1;lx < n;lx++){
if(nxt[lx-1] == n) nd[lx] = nd[lx-1];
else nd[lx] = CUpdate(nd[lx-1], nxt[lx-1], 1);
}
#ifdef DEBUG
for(int lx = 0;lx < n;lx++){
Print(nd[lx]);
puts("");
}
#endif
int q; scanf("%d", &q);
while(q--){
int a, b; scanf("%d %d", &a, &b);
a--, b--;
printf("%d\n", Query(nd[a], a, b));
}
return 0;
}
|