一 题目
二 分析
主席树的运用。
这题首先应该考虑的是，如何分出种类数？再就是考虑如何维护区间信息？
最开始想的是直接离散化后用权值线段树建主席树，发现不行，因为假如$ [l,r] $的值在$l$之前已经出现了，那么直接用历史版本的相减肯定会出问题。所以排除此方法。
所以在维护历史版本的时候要同时更新各个种类值的最新位置。这样就保证了，在给定$[l,r]$后就可以根据$r$位置的权值线段树，找到比$l$大的数目就是答案。
三 AC代码
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int MAXN = 3e4 + 15; 6 int n, q, a[MAXN], root[MAXN], tot; 7 struct Node 8 { 9 int l, r, c; 10 }T[MAXN*30]; 11 12 void build(int &rt, int l, int r) 13 { 14 T[++tot].c = 0; 15 rt = tot; 16 if(l == r) return; 17 int mid = (l+r)>>1; 18 build(T[rt].l, l, mid); 19 build(T[rt].r, mid + 1, r); 20 } 21 void update(int &cur, int pre,int l, int r, int pos, int val) 22 { 23 T[++tot] = T[pre]; 24 cur = tot; 25 T[cur].c += val; 26 if(l == r) return; 27 int m = (l + r) >> 1; 28 if(pos <= m) 29 update(T[cur].l, T[pre].l, l, m, pos, val); 30 else 31 update(T[cur].r, T[pre].r, m + 1, r, pos, val); 32 } 33 int query(int rt, int l, int r, int pos) 34 { 35 36 if(l >= pos) return T[rt].c; 37 int ans = 0; 38 int m = (l + r) >>1; 39 if(pos <= m) 40 { 41 ans += T[T[rt].r].c; 42 ans += query(T[rt].l, l, m, pos); 43 } 44 else 45 { 46 ans += query(T[rt].r, m + 1, r, pos); 47 } 48 return ans; 49 } 50 int main() 51 { 52 //freopen("in.txt", "r", stdin); 53 scanf("%d", &n); 54 for(int i = 1; i <= n; i++) 55 { 56 scanf("%d", &a[i]); 57 } 58 tot = 0; 59 build(root[0], 1, n); 60 map<int, int> mp; 61 for(int i = 1; i <= n; i++) 62 { 63 if(mp.find(a[i]) == mp.end()) 64 update(root[i], root[i-1], 1, n, i, 1); 65 else 66 { 67 int tmp; 68 update(tmp, root[i-1], 1, n, mp[a[i]], -1); 69 update(root[i], tmp, 1, n, i, 1); 70 } 71 mp[a[i]] = i; 72 } 73 scanf("%d", &q); 74 for(int i = 0; i < q; i++) 75 { 76 int x, y; 77 scanf("%d%d", &x, &y); 78 printf("%d ", query(root[y], 1, n, x)); 79 } 80 return 0; 81 }