SPOJ3267 D-Query 树状数组离线操作 或 主席树 查询某一区间内有多少不同的数

D-Query

看的网上的，不甚理解。代码中有注释。维护树状数组C[i]， sum(x)指 A[1:x]中有几个不同的数字

DQUERY - D-query

#sorting  #tree EnglishVietnamese

Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, ..., aj.

Input

Line 1: n (1 ≤ n ≤ 30000).Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output

For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, ..., aj in a single line.

Example

Input 5 1 1 2 1 3 3 1 5 2 4 3 5 Output 3 2 3

//树状数组离线操作 #include <cstdio> #include <cstring> #include <algorithm> #include <map> #define M 200007 using namespace std; //cnt[i]存第i次询问结果，l,r分别存询问的边界，A,C是树状数组里边的 const int N = 3e4 + 7; int l[M], r[M], A[N], id[M], n; //pos[i]指数字i在A[]中的位置，拖i在A中重复出现，维护pos[i]尽量靠后 int C[N], cnt[M], pos[1000007]; //pos的大小取决于A[i]的范围，可以换为数组 inline int lowbit(int x) { return x & (-x); } void add(int x, int val) { for (int i = x; i <= n; i += lowbit(i) ) C[i] += val; } int sum(int x) { int res = 0; for (int i = x; i > 0; i -= lowbit(i)) res += C[i]; return res; } bool cmp(int i, int j) { return r[i] < r[j]; } int main() { while(~scanf("%d", &n)) { memset(C, 0, sizeof C); //树状数组 memset(pos, 0, sizeof pos); for (int i = 1; i <= n; ++i) { scanf("%d", A + i); //一维数组存数，和算法入门经典里讲的一样 add(i, 1); // if (!pos[A[i]]) pos[A[i]] = i; int m; scanf("%d", &m); for (int i = 1; i <= m; ++i) { scanf("%d%d", l + i, r + i); id[i] = i; //记下查询顺序 } //接下来根据查询的右边界对查询顺序排序 sort(id + 1, id + 1 + m, cmp); //第一次见这种操作是看acdart直播时 /*主要思想是将计数尽可能拖到后面来*/ int right = 1; for (int i = 1; i <= m; ++i) { int x = id[i]; while(right <= r[x]) { if (pos[A[right] != right]) { add(pos[A[right]], -1); //在后面出现了，前面的计数抵消。在后面计数，保证查询区间里的数不遗漏 pos[A[right]] = right; } ++right; } right = r[x]; cnt[x] = sum(r[x]) - sum(l[x] - 1); } for (int i = 1; i <= m; ++i) printf("%d\n", cnt[i]); } } return 0; }

杭电hdu4417也可以用树状数组离线操作解决

#include <cstdio> #include <cstring> #include <algorithm> #define N 100007 int bit[N], ary[N], cnt[N], n; struct Node { int val, pos; bool operator < (const Node tmp) const { return val < tmp.val; } }a[N]; struct Query { int le, ri, id, h; bool operator < (const Query tmp) const { return h < tmp.h; } }q[N]; inline int lowbit(int x) { return x & -x; } void add(int pos, int val) { for(int i = pos; i <= n; i += lowbit(i)) bit[i] += val; } int sum(int pos) { int ret = 0; for (int i = pos; i > 0; i -= lowbit(i)) ret += bit[i]; return ret; } int main() { int T, kase = 0; scanf("%d", &T); while(T-- > 0) { memset(bit, 0, sizeof bit); int m; scanf("%d%d", &n, &m); for (int i= 1; i <= n; ++i) { scanf("%d", &a[i].val); a[i].pos = i; } for (int i = 1; i <= m; ++i) { scanf("%d%d%d", &q[i].le, &q[i].ri, &q[i].h); q[i].id = i; } std::sort(a + 1, a + 1 + n); std::sort(q + 1, q + 1 + m); int k = 1; for (int i = 1; i <= m; ++i) { while(k <= n && a[k].val <= q[i].h) { add(a[k].pos, 1); ++k; } cnt[q[i].id] = sum(q[i].ri + 1) - sum(q[i].le); } printf("Case %d:\n", ++kase); for (int i = 1; i <= m; ++i) printf("%d\n", cnt[i]); } }

主席树解法

//求区间不同数的个数 #define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <algorithm> #include <cstring> #include <map> using namespace std; const int N = 30007; //最多N个数 const int M = N * 100; int n, q, tot; //n个数，q次询问 int a[N]; //原始数组 //T[i]保存[1,i]中有多少个不同的数 int T[M], lson[M], rson[M], c[M]; //c数组可能就是主席树要维护的值，比如本题维护区间数的个数 int build(int l, int r) { //返回[l,r]的父节点。建一棵非叶子节点都有两个孩子的树 int rt = tot++; //tot从0开始，用的节点数。最终tot=2*n-1 c[rt] = 0; if (l != r) { int mid = l + r >> 1; lson[rt] = build(l, mid); //lson用来保存父亲节点rt的左孩子的索引 rson[rt] = build(mid + 1, r); } return rt; } int update(int rt, int pos, int val) { int newRoot = tot++, tmp = newRoot; //newRoot申请新的节点 c[newRoot] = c[rt] + val;//主席树可以加减。同构 int l = 1, r = n; while (l < r) {//二分建树，只是写法形式上和 mid = l + r >> 1然后左右建树不同 int mid = l + r >> 1; if (pos <= mid) { lson[newRoot] = tot++;//新建左子树 rson[newRoot] = rson[rt];//右子树复用前一棵线段树的，这样就节省了空间，不至于MLE newRoot = lson[newRoot]; rt = lson[rt]; r = mid; } else { rson[newRoot] = tot++; lson[newRoot] = lson[rt]; newRoot = rson[newRoot]; //上句要用到，newRoot，so,不能慌着更新newRoot rt = rson[rt];//更新当前根节点 l = mid + 1; } c[newRoot] = c[rt] + val;//新节点的值，由之前的节点更新而来 } return tmp; //返回新建树的根节点 } //询问l到pos有多少个不同的数, rt = T[l] int query(int rt, int pos) { int res = 0; int l = 1, r = n; while (pos < r) { int mid = l + r >> 1; if (pos <= mid) {//在左子树中查 r = mid; rt = lson[rt]; } else { //在右子树中搜 res += c[lson[rt]]; rt = rson[rt]; l = mid + 1; } } return res + c[rt]; } int main() { while (~scanf("%d", &n)) { tot = 0; for (int i = 1; i <= n; ++i) scanf("%d", a + i); T[n + 1] = build(1, n); //难道是先建一棵树 map<int, int> mp; //主席树是函数式编程，可能需要映射吧 for (int i = n; i >= 1; --i) { if (mp.find(a[i]) == mp.end()) { T[i] = update(T[i + 1], i, 1); //每次调用都新建一棵线段树。update返回的是新建树的根节点 } else { int tmp = update(T[i + 1], mp[a[i]], -1); //若a[i]不是很大，可用数组代替映射 T[i] = update(tmp, i, 1); } mp[a[i]] = i; //若之前存在a[i]，那么a[i]将被覆盖了，第二值保存的是较小的i } scanf("%d", &q); while (q--) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", query(T[l], r));//由l确定在那棵线段树中查询 } } return 0; }