while (l < h-1) { int m = l+h >> 1, lcnt = 0; for (int t : span(pos, npos)) lcnt += seg[seg[t].ch[0]].cnt; for (int t : span(neg, nneg)) lcnt -= seg[seg[t].ch[0]].cnt; int d = k >= lcnt; if (d) l = m, k -= lcnt; else h = m; for (int &t : span(pos, npos)) t = seg[t].ch[d]; for (int &t : span(neg, nneg)) t = seg[t].ch[d]; }
namespace { intri(){ int m = 0, s = 0; unsigned c; while ((c = getchar())-'0' >= 10u) m = c == '-'; for (; c-'0' < 10u; c = getchar()) s = s*10+c-'0'; return m ? -s : s; }
constint N = 100000, M = 100000, LOG2N = 32-__builtin_clz(N), LOG2NM = 32-__builtin_clz(N+M-1); int a[N], b[N+M], roots[N], pos[LOG2N], neg[LOG2N], allo; structOp {bool modify; int l, r, k; } q[M]; structSegment {int ch[2], cnt; } seg[(N+M*2)*LOG2N*LOG2NM];
voidadd(int n, int nv, int i, int v){ int x = lower_bound(b, b+nv, a[i]) - b; for (; i < n; i |= i+1) { int l = 0, r = nv, *t = &roots[i]; for(;;) { if (!*t) *t = ++allo; seg[*t].cnt += v; if (l == r-1) break; int m = l+r >> 1, d = x >= m; if (d) l = m; else r = m; t = &seg[*t].ch[d]; } } }
intkth(int npos, int nneg, int l, int h, int k){ while (l < h-1) { int m = l+h >> 1, lcnt = 0; for (int t : span(pos, npos)) lcnt += seg[seg[t].ch[0]].cnt; for (int t : span(neg, nneg)) lcnt -= seg[seg[t].ch[0]].cnt; int d = k >= lcnt; if (d) l = m, k -= lcnt; else h = m; for (int &t : span(pos, npos)) t = seg[t].ch[d]; for (int &t : span(neg, nneg)) t = seg[t].ch[d]; } return l; } }
intmain(){ int n = ri(), m = ri(), nv = n; REP(i, n) a[i] = b[i] = ri(); REP(i, m) { char c; while (c = getchar_unlocked(), c != 'C' && c != 'Q'); if (c == 'C') { q[i] = {true, ri()-1, -1, ri()}; b[nv++] = q[i].k; } else q[i] = {false, ri()-1, ri(), ri()}; }
// persistent segment tree #include<algorithm> #include<cstdio> usingnamespacestd;
#define REP(i, n) for (int i = 0; i < (n); i++)
intri(){ int m = 0, s = 0; unsigned c; while ((c = getchar())-'0' >= 10u) m = c == '-'; for (; c-'0' < 10u; c = getchar()) s = s*10+c-'0'; return m ? -s : s; }
constint N = 200000, M = 200000, LOG2N = 32-__builtin_clz(N-1); int a[N], b[N], roots[N+1], allo; structSegment {int ch[2], cnt; } seg[N*2+M*LOG2N];
voidbuild(int &t, int l, int r){ t = ++allo; if (l < r-1) { int m = l+r >> 1; build(seg[t].ch[0], l, m); build(seg[t].ch[1], m, r); } }
voidadd(int *t, int u, int l, int r, int v){ while (l < r-1) { *t = ++allo; seg[*t].cnt = seg[u].cnt+1; int m = l+r >> 1, d = v >= m; if (d) l = m; else r = m; seg[*t].ch[d^1] = seg[u].ch[d^1]; t = &seg[*t].ch[d]; u = seg[u].ch[d]; } *t = ++allo; seg[*t].cnt = seg[u].cnt+1; }
intkth(int t, int u, int l, int r, int k){ while (l < r-1) { int m = l+r >> 1, lcnt = seg[seg[t].ch[0]].cnt-seg[seg[u].ch[0]].cnt, d = k >= lcnt; if (d) l = m, k -= lcnt; else r = m; t = seg[t].ch[d]; u = seg[u].ch[d]; } return l; }
intmain(){ int n = ri(), m = ri(); REP(i, n) { a[i] = ri(); b[i] = a[i]; } sort(b, b+n); int nn = unique(b, b+n) - b; build(roots[0], 0, nn); REP(i, n) { int v = lower_bound(b, b+nn, a[i]) - b; add(&roots[i+1], roots[i], 0, nn, v); } while (m--) { int l = ri(), r = ri(), k = ri(); printf("%d\n", b[kth(roots[r], roots[l-1], 0, nn, k-1)]); } }
Wavelet tree及变体
Wavelet tree
来自R. Grossi, A. Gupta, and J. S. Vitter, High-orderentropy-compressed text indexes, Proceedings of the 14th AnnualSIAM/ACM Symposium on Discrete Algorithms (SODA), January 2003,841-850.
Wavelet tree是一种succinct data structure,可以在O(logσ)时间求rank、select、和kth操作,其中σ是字符集大小。树的每个节点描述一个值域区间,存储区间内所有元素。根节点描述原数组。选取一个2的幂2^(ceil(log2(r-l))-1)把区间划分成[l,2^(ceil(log2(r-l))-1))和[l+2^(ceil(log2(r-l))-1),r)两部分,把元素分配给左右两个孩子。递归该分配过程,直到值域区间[l,r)是单位区间。
使用range tree fractionalcascading技巧,节点存储另一个数组记录前i个元素中有几个分配到左孩子(wavelettree的rank0询问)。对于一个询问[l,r),可以O(1)知道落在左孩子值域的元素个数,从而答案在左孩子还是右孩子。另外还能知道[l,r)应该映射为左(或右)孩子的哪一个区间。
namespace { intri(){ int m = 0, s = 0; unsigned c; while ((c = getchar())-'0' >= 10u) m = c == '-'; for (; c-'0' < 10u; c = getchar()) s = s*10+c-'0'; return m ? -s : s; }
structWaveletMatrix { int height; vector<vector<uint64_t>> b; vector<vector<int>> bcnt; vector<int> z; WaveletMatrix(span<int> a, int sigma) : height(sigma == 1 ? 1 : 32-__builtin_clz(sigma-1)), b(height, vector<uint64_t>(a.size()/64+1)), bcnt(height, vector<int>(a.size()/64+1)), z(height) { int n = a.size(); for (int i = height; i--; ) { for (int j = 0; j < a.size(); j++) b[i][j/64] |= uint64_t(a[j]>>i & 1) << j%64; for (int j = 1; j < b[i].size(); j++) bcnt[i][j] = bcnt[i][j-1] + __builtin_popcountll(b[i][j-1]); z[i] = stable_partition(a.begin(), a.end(), [&](int x) { return !(x>>i&1); }) - a.begin(); } } intrank1(int i, int x)const{ return bcnt[i][x/64] + __builtin_popcountll(b[i][x/64] & ((uint64_t(1) << x%64) - 1)); }; intkth(int l, int r, int k)const{ int res = 0; for (int i = height; i--; ) { int rnkl = rank1(i, l), rnkr = rank1(i, r), cnt0 = r-rnkr-(l-rnkl); if (k < cnt0) { l -= rnkl; r -= rnkr; } else { k -= cnt0; l = z[i]+rnkl; r = z[i]+rnkr; res |= 1 << i; } } return res; } }; }
intmain(){ int n = ri(), m = ri(); auto a = std::make_unique_for_overwrite<int[]>(n); auto b = std::make_unique_for_overwrite<int[]>(n); REP(i, n) a[i] = b[i] = ri(); sort(b.get(), b.get()+n); int nn = unique(b.get(), b.get()+n) - b.get(); REP(i, n) a[i] = lower_bound(b.get(), b.get()+nn, a[i]) - b.get(); WaveletMatrix wm(span(a.get(), n), nn); while (m--) { int l = ri()-1, r = ri(), k = ri(); printf("%d\n", b[wm.kth(l, r, k-1)]); } }
#define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) for (int i = 0; i < (n); i++)
constint N = 200000, M = 200000;
namespace { intri(){ int m = 0, s = 0; unsigned c; while ((c = getchar())-'0' >= 10u) m = c == '-'; for (; c-'0' < 10u; c = getchar()) s = s*10+c-'0'; return m ? -s : s; }
#define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) for (int i = 0; i < (n); i++)
constint N = 100000, M = 100000;
namespace { intri(){ int m = 0, s = 0; unsigned c; while ((c = getchar_unlocked())-'0' >= 10u) m = c == '-'; for (; c-'0' < 10u; c = getchar_unlocked()) s = s*10+c-'0'; return m ? -s : s; }
intri(){ int m = 0, s = 0; unsigned c; while ((c = getchar())-'0' >= 10u) m = c == '-'; for (; c-'0' < 10u; c = getchar()) s = s*10+c-'0'; return m ? -s : s; }
constint N = 200000, M = 200000; int a[N], b[N], block[N], c1[N], c2[N], block_size; structQuery { int l, r, k, id, ans; booloperator<(const Query &o) const { int i = block[l], j = block[o.l]; if (i != j) return i < j; return i & 1 ? r < o.r : r > o.r; } } qs[M];
staticvoidadd(int i, int d){ c1[a[i]] += d; c2[block[a[i]]] += d; }
int l = 0, r = 0; REP(i, m) { while (qs[i].l < l) add(--l, 1); while (r < qs[i].r) add(r++, 1); while (l < qs[i].l) add(l++, -1); while (qs[i].r < r) add(--r, -1); int x = 0, k = qs[i].k; while (c2[x] < k) k -= c2[x++]; for (int j = x*block_size; ; j++) if ((k -= c1[j]) <= 0) { qs[i].ans = j; break; } } REP(i, m) a[qs[i].id] = b[qs[i].ans]; REP(i, m) printf("%d\n", a[i]); }