题意
给出一个数列，问你好多次在这个序列上某一段里面有多少不同的数。数列没有发生更新。
思路
因为没有发生更新，所以可以采用这样的一种方法：
首先接收好全部的查询请求，然后把查询请求按照右端点从小到大排列。接下来，我们已Sample为例“1 2 3 4 3 5”，首先看1，这个数没有出现过，我们给一号位置标记一个1，然后看2，没出现过，标记一个1，然后3号位的3没出现过，标上1，然后四号位标1，然后到了五号位，我们发现3出现过了，所以要把之前出现过的三号位的1抹去，给5号位标上1，到了六号位，是5，没出现过，标记上1。
我们发现，在上面这个过程中，只要我们照着这种方法来标记，就可以确保检查到i号位的时候，所有1～i这个区间的询问都是准确的，也就是说我们一次处理一位的标记情况，之后就可以处理掉所有以这一位为右端点的询问，询问的结果就是被询问的那一段区间的标记之和。区间和当然要优化，可以使用BIT。
代码
|
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 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; #define MAXN 50005 #pragma mark - Binary Indexed Tree (BIT) 1D //index begins from ONE //init:memset BIT,set BIT_size int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int int BIT_size;//should assign when use inline int lowbit(int a){ return a & (-a); } void BIT_modify(int pos,int delta){//type of delta may need to modify for (int x = pos; x <= BIT_size; x += lowbit(x)) { BIT[x] += delta; } } int BIT_sum(int pos){//return type may alter int ret = 0; for (int x = pos; x > 0; x -= lowbit(x)) { ret += BIT[x]; } return ret; } #pragma mark - int prv[MAXN*20]; int seq[MAXN]; int res[MAXN*4]; struct Query{ int l,r,id,res; } query[MAXN*4]; bool cmp1(const Query &a,const Query &b){ return a.r < b.r; } bool cmp2(const Query &a,const Query &b){ return a.id < b.id; } int main(){ int n; while(scanf(" %d",&n) != EOF){ memset(BIT, 0, sizeof(BIT)); BIT_size = n; memset(prv, 0, sizeof(prv)); for (int i = 1; i <= n; i++) { scanf(" %d",&seq[i]); } int q; scanf(" %d",&q); for (int i = 1; i <= q; i++) { scanf(" %d %d",&query[i].l,&query[i].r); query[i].id = i; } sort(query+1, query+1+q,cmp1); int k = 1; for (int i = 1; i <= n; i++) { if (prv[seq[i]]) { BIT_modify(prv[seq[i]], -1); } BIT_modify(prv[seq[i]] = i, 1); for (; query[k].r == i; k++) { query[k].res = BIT_sum(i) - BIT_sum(query[k].l-1); } } sort(query+1, query+1+q, cmp2); for (int i = 1; i <= q; i++) { printf("%d\n",query[i].res); } } return 0; } |