首页 > 代码库 > [SPOJ DQUERY] D-query（树状数组，离线）

[SPOJ DQUERY] D-query（树状数组，离线）

2024-09-20 22:47:59   217人阅读

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

题意：给定数列，q次询问，问区间内不同数字的个数。

可以用主席树，但是还有更好写的办法。

离线存下所有的询问，按照询问右端点从小到大排序。

用树状数组标记“某个值在区间[1,r]中出现的最后的位置”。这样可以将r从左向右平移，每一个r更新所有右边界为r的查询。

因为某值出现总是尽可能向后，所以这样可以保证不会重复。

用一个map来记录某个值出现的位置，然后移动的时候更新树状数组就行了。整体复杂度就是O(n*logn+Q)的。

 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef struct Event {
 5     int l, r, id;
 6 }Event;
 7 const int maxn = 200100;
 8 int n, q, a[maxn];
 9 int bit[maxn];
10 vector<Event> event;
11 int ret[maxn];
12 unordered_map<int, int> vis;
13 
14 bool cmp(Event a, Event b) { return a.r < b.r; }
15 int lowbit(int x) { return x & (-x); }
16 void add(int i, int v) { for(; i <= n; i+=lowbit(i)) bit[i] += v; }
17 int sum(int i) { int ret = 0; for(; i > 0; i-=lowbit(i)) ret += bit[i]; return ret; }
18 
19 int main() {
20     // freopen("in", "r", stdin);
21     int l, r;
22     while(~scanf("%d",&n)) {
23         for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
24         event.clear(); vis.clear();
25         memset(bit, 0, sizeof(bit));
26         scanf("%d", &q);
27         for(int i = 1; i <= q; i++) {
28             scanf("%d%d",&l,&r);
29             event.push_back(Event{l,r,i});
30         }
31         sort(event.begin(), event.end(), cmp);
32         r = 0;
33         for(int i = 1; i <= n; i++) {
34             if(vis.find(a[i]) == vis.end()) {
35                 vis[a[i]] = i;
36                 add(i, 1);
37             }
38             else {
39                 add(vis[a[i]], -1);
40                 vis[a[i]] = i;
41                 add(i, 1);
42             }
43             while(event[r].r == i) {
44                 ret[event[r].id] = sum(event[r].r) - sum(event[r].l-1);
45                 r++;
46             }
47         }
48         for(int i = 1; i <= q; i++) printf("%d\n", ret[i]);
49     }
50     return 0;
51 }

 

[SPOJ DQUERY] D-query（树状数组，离线）


联系
我们