?
主席树详解
每次插入logn个点 这样就不需要重新建树了。
#pragma comment(linker, /STACK:1024000000,1024000000) #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; template inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template inline void pt(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) pt(x / 10); putchar(x % 10 + '0'); } typedef long long ll; typedef pair pii; const int N = 100000 + 100; #define L(x) tree[x].lson #define R(x) tree[x].rson #define S(x) tree[x].sum struct Node { int lson, rson; int sum; }tree[N << 5]; int top; vector Hash; int gethash(int val) { return lower_bound(Hash.begin(), Hash.end(), val) - Hash.begin() + 1; } int build(int l, int r) { int id = ++top; S(id) = 0; if (l < r) { int mid = (l + r) >> 1; L(id) = build(l, mid); R(id) = build(mid + 1, r); } return id; } int update(int pre, int l, int r, int val) { int id = ++top; L(id) = L(pre); R(id) = R(pre); S(id) = S(pre) + 1; if (l < r) { int mid = (l + r) >> 1; if (val <= mid) L(id) = update(L(pre), l, mid, val); else R(id) = update(R(pre), mid + 1, r, val); } return id; } int query(int old, int cur, int l, int r, int k) { if (l >= r)return l; int mid = (l + r) >> 1; int siz = S(L(cur)) - S(L(old)); if (siz < k) return query(R(old), R(cur), mid + 1, r, k - siz); else return query(L(old), L(cur), l, mid, k); } int n, q; int a[N]; int T[N]; int main() { int cas; rd(cas); while (cas--) { rd(n); rd(q); Hash.clear(); top = 0; for (int i = 1; i <= n; i++) { rd(a[i]); Hash.push_back(a[i]); } sort(Hash.begin(), Hash.end()); Hash.erase(unique(Hash.begin(), Hash.end()), Hash.end()); T[0] = build(1, Hash.size()); for (int i = 1; i <= n; i++) { T[i] = update(T[i - 1], 1, Hash.size(), gethash(a[i])); } while (q--) { int l, r, k; rd(l); rd(r); rd(k); int id = query(T[l - 1], T[r], 1, Hash.size(), k); pt(Hash[id - 1]); puts(); } } return 0; }