https://www.cnblogs.com/zyf0163/p/4749042.html 主要是看的这篇
https://blog.csdn.net/weixin_42165981/article/details/81154209
http://acm.hdu.edu.cn/showproblem.php?pid=2665
求区间第K大。注意c++中&的作用。ls[]与rs[]都是通过这个更新的。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 100000 + 5; int a[N], b[N], rt[N * 20], ls[N * 20], rs[N * 20], sum[N * 20]; int n, k, tot, sz, ql, qr, x, q, T; void Build(int& o, int l, int r){ o = ++tot; sum[o] = 0; if(l == r) return; int m = (l + r) >> 1; Build(ls[o], l, m); Build(rs[o], m + 1, r); } void update(int& o, int l, int r, int last, int p){ o = ++tot; ls[o] = ls[last]; rs[o] = rs[last]; sum[o] = sum[last] + 1; if(l == r) return; int m = (l + r) >> 1; if(p <= m) update(ls[o], l, m, ls[last], p); else update(rs[o], m + 1, r, rs[last], p); } int query(int ss, int tt, int l, int r, int k) { if(l == r) return l; int m = (l + r) >> 1; int cnt = sum[ls[tt]] - sum[ls[ss]]; if(k <= cnt) return query(ls[ss], ls[tt], l, m, k); else return query(rs[ss], rs[tt], m + 1, r, k - cnt); } void work(){ scanf("%d%d%d", &ql, &qr, &x); int ans = query(rt[ql - 1], rt[qr], 1, sz, x); printf("%d\n", b[ans]); } int main(){ scanf("%d", &T); while(T--){ scanf("%d%d", &n, &q); for(int i = 1; i <= n; i ++) scanf("%d", a + i), b[i] = a[i]; sort(b + 1, b + n + 1); sz = unique(b + 1, b + n + 1) - (b + 1); tot = 0; Build(rt[0],1, sz); //for(int i = 0; i <= 4 * n; i ++)printf("%d,rt = %d,ls = %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]); for(int i = 1; i <= n; i ++) a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b; for(int i = 1; i <= n; i ++) update(rt[i], 1, sz, rt[i - 1], a[i]); // for(int i = 0; i <= 5 * n; i ++) printf("%d,rt = %d,ls = %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]); while(q --) work(); } return 0; }
https://www.spoj.com/problems/DQUERY/en/
求一段区间内 distinct的数字。可以用树状数组做。
每次相当于去这个数字最后出现的位置，如果没出现过，就在那个位置加一，如果出现过要在之前的位置减一，在新位置加一。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 3e4 + 5; int a[N], b[N], rt[N * 20], ls[N * 20], rs[N * 20], sum[N * 20]; int ind[N]; int n, k, tot, sz, ql, qr, x, q, T; void Build(int& o, int l, int r){ o = ++tot; sum[o] = 0; if(l == r) return; int m = (l + r) >> 1; Build(ls[o], l, m); Build(rs[o], m + 1, r); } void update(int& o, int l, int r, int last, int p, int v){ o = ++tot; ls[o] = ls[last]; rs[o] = rs[last]; sum[o] = sum[last] + v; if(l == r) return; int m = (l + r) >> 1; if(p <= m) update(ls[o], l, m, ls[last], p, v); else update(rs[o], m + 1, r, rs[last], p, v); } //int query(int ss, int tt, int l, int r, int k) { // if(l == r) return l; // int m = (l + r) >> 1; // int cnt = sum[ls[tt]] - sum[ls[ss]]; // if(k <= cnt) return query(ls[ss], ls[tt], l, m, k); // else return query(rs[ss], rs[tt], m + 1, r, k - cnt); //} int query(int l, int r, int root, int left) { if(l >= left) return sum[root]; int mid = (l + r) >> 1; if(mid >= left) return query(l, mid, ls[root], left) + sum[rs[root] ]; else return query(mid + 1, r, rs[root], left); } void work(){ scanf("%d%d", &ql, &qr); int ans = query(1, sz, rt[qr], ql); printf("%d\n", ans); } int main(){ scanf("%d", &n); for(int i = 1; i <= n; i ++) scanf("%d", a + i), b[i] = a[i]; memset(ind, 0, sizeof(ind)); sort(b + 1, b + n + 1); sz = unique(b + 1, b + n + 1) - (b + 1); tot = 0; Build(rt[0], 1, sz); int tmp; //for(int i = 0; i <= 4 * n; i ++)printf("%d,rt = %d,ls = %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]); for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b; for(int i = 1; i <= n; i ++) { if(ind[a[i] ] == 0) update(rt[i], 1, sz, rt[i - 1], i, 1); else { update(tmp, 1, sz, rt[i - 1], ind[a[i]], -1); update(rt[i], 1, sz, tmp, i, 1); } ind[a[i] ] = i; } // for(int i = 0; i <= 5 * n; i ++) printf("%d,rt = %d,ls = %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]); scanf("%d", &q); while(q --) work(); return 0; }
原文：https://www.cnblogs.com/downrainsun/p/11200405.html