首页 > 代码库 > SPOJ - DQUERY: D-query 离线处理 + 树状数组

SPOJ - DQUERY: D-query 离线处理 + 树状数组

2024-11-17 21:29:02   202人阅读

题目链接：https://vjudge.net/problem/SPOJ-DQUERY

 

题意：给定数字序列，求任意区间内的不同数字的个数

 

解法：用树状数组维护 1 ~ i 的区间内不同数字个数的前缀和，首要解决的问题就是同一区间内相同数字统计时相互影响的问题，解决方法如下：离线存储查询的区间，对查询区间按照左端点排序，这样可以优先处理左边的           元素；然后预处理出每一元素下一跳到相同元素的 nxt[]; 这样随着坐标轴指针 l 的移动，l 左边的元素将不会产生任何影响，因为所产生的影响会在前缀和的做差运算中抵消；只需要对 l 指针左区间的元素的下一跳的位           置进行 add + 1 操作，从而更新当前查询区间的信息。 

 

BIT代码实现：

技术分享
 1 //190ms    19.5MB 2 #include <bits/stdc++.h> 3 using namespace std; 4  5 const int N = 30010; 6 const int M = 200010; 7 int a[N], bit[N]; 8  9 void init() {10     memset(bit, 0, sizeof(bit));11 }12 13 int lowbit(int x) {14     return x & -x;15 }16 17 void add(int x, int val) {18     while(x < N) {19         bit[x] += val;20         x += lowbit(x);21     }22 }23 24 int sum(int x) {25     int ret = 0;26     while(x > 0) {27         ret += bit[x];28         x -= lowbit(x);29     }30     return ret;31 }32 33 struct Query{34     int l, r, p;35     bool operator < (const Query& p)const{36         return l < p.l;37     }38 } query[M];39 int n, q;40 map<int, int> mp;41 int nxt[N], ans[M];42 43 int main()44 {45     scanf("%d", &n);46     mp.clear();47     init();48     for (int i = 1; i <= n; ++ i) {49         scanf("%d", &a[i]);50         if(mp.find(a[i]) == mp.end()) {51             mp[a[i]] = i;52             add(i, 1);53         }54     }55     mp.clear();56     for (int i = n; i >= 1; -- i) {57         if(mp.find(a[i]) == mp.end()) nxt[i] = n + 1;58         else nxt[i] = mp[a[i]];59         mp[a[i]] = i;60     }61     scanf("%d", &q);62     for (int i = 1; i <= q; ++ i) {63         scanf("%d%d", &query[i].l, &query[i].r);64         query[i].p = i;65     }66     sort(query+1, query+1+q);67     int pp = 1;68     for (int i = 1; i <= q; ++ i) {69         while(pp<=n && pp < query[i].l) add(nxt[pp++], 1);70         ans[query[i].p] = sum(query[i].r) - sum(query[i].l-1);71     }72     for (int i = 1; i <= q; ++ i) printf("%d\n", ans[i]);73     return 0;74 }
View Code

 

SPOJ - DQUERY: D-query 离线处理 + 树状数组


联系
我们