题意
给出一个数列,问你好多次在这个序列上某一段里面有多少不同的数。数列没有发生更新。
思路
因为没有发生更新,所以可以采用这样的一种方法:
首先接收好全部的查询请求,然后把查询请求按照右端点从小到大排列。接下来,我们已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; } |
September 05, 2015
[…] 但是对于每一棵子树都统计一次,复杂度很大,显然需要再优化。优化的方法就是“DFS序把树压平”然后“离线处理”。首先遍历parent树,纪录每一个节点进入时的DFN和出去时的DFN,从进去到出去这两个DFN之间的所有节点(包括出入两个节点)显然就是parent的子树了。现在我们的问题就转变为了在某个数组上一段给定的区间求有多少个不同的数字,而且还是离线处理,这种问题可以使用一种O(n)的处理方法,详情可以参考BZOJ 1878 HH的项链。 […]