题目：https://www.luogu.org/problemnew/show/P1972
题意：给定一个长度为n的序列，数字表示珠子的种类。m次查询每次询问给定区间内珠子的种类数。
思路：可以说是运用了前缀和的思想吧。从前到后的去处理查询，而对于某一个查询区间，如果某一个种类出现了多次的话我们只需要计算最后一次出现。
用query(x)表示1~x区间内的种类数，其中对每个种类我们只标记最后一次出现。也就是说顺序遍历的时候如果又出现了就把前面的清空，标记当前位置。
如果查询的区间是l~r那么答案就是query(r) - query(l - 1)。
所以首先需要把查询按照右端点从小到大排序。每次只需要更新上一次右端点到这一次右端点这一段区间，同时要标记每一个种类最近一次出现的位置，用于清空。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<stack> 10 #include<queue> 11 #include<iostream> 12 13 #define inf 0x3f3f3f3f 14 using namespace std; 15 typedef long long LL; 16 typedef pair<int, int> pr; 17 18 int n, m; 19 const int maxn = 5e5 + 5; 20 struct node{ 21 int l, r, id, ans; 22 }q[maxn]; 23 int neck[maxn]; 24 int sum[maxn << 2]; 25 const int maxnum = 1e6 + 5; 26 int pos[maxnum]; 27 28 bool cmp(node a, node b) 29 { 30 return a.r < b.r; 31 } 32 33 bool cmp1(node a, node b) 34 { 35 return a.id < b.id; 36 } 37 38 39 void add(int rt, int val) 40 { 41 while(rt <= n){ 42 sum[rt] += val; 43 rt += (rt & -rt); 44 } 45 } 46 47 int query(int rt) 48 { 49 int ans = 0; 50 while(rt){ 51 ans += sum[rt]; 52 rt -= (rt & -rt); 53 } 54 return ans; 55 } 56 57 int main() 58 { 59 scanf("%d", &n); 60 for(int i = 1; i <= n; i++){ 61 scanf("%d", &neck[i]); 62 } 63 scanf("%d", &m); 64 for(int i = 0; i < m; i++){ 65 scanf("%d%d", &q[i].l, &q[i].r); 66 q[i].id = i; 67 } 68 sort(q, q + m, cmp); 69 70 int nxt = 1; 71 for(int i = 0; i < m; i++){ 72 int r = q[i].r; 73 for(int j = nxt; j <= r; j++){ 74 if(pos[neck[j]]){ 75 add(pos[neck[j]], -1); 76 } 77 add(j, 1); 78 pos[neck[j]] = j; 79 } 80 nxt = r + 1; 81 q[i].ans = query(q[i].r) - query(q[i].l - 1); 82 } 83 sort(q, q + m, cmp1); 84 for(int i = 0; i < m; i++){ 85 printf("%d ", q[i].ans); 86 } 87 return 0; 88 }