POJ 2104
/** POJ 2104 区间第K小,主席数模板 **/ #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #define INF 0x3f3f3f3f #define eps 1e-8 using namespace std; #define ll long long const ll MAXN = 100005; const ll MAXM = 2000005; vector<ll> ha; ll a[MAXN]; ll tot; struct NODE { ll count; ll left, right; }; ll root[MAXN]; NODE node[MAXM]; ll null; ll newnode(ll count, ll left, ll right) { node[tot].count=count; node[tot].left=left; node[tot].right=right; return tot++; } ll ins(ll rt, ll l, ll r, ll k) { if (l <= k && k <= r) { if (l == r) { return newnode(node[rt].count + 1, 0, 0); } ll m = (l + r) >> 1; return newnode(node[rt].count + 1, ins(node[rt].left, l, m, k), ins(node[rt].right, m + 1, r, k)); } return rt; } ll query(ll p, ll q, ll l, ll r, ll k) { if (l == r) { return ha[l]; } ll m = (l + r) >> 1; ll cot = node[node[q].left].count - node[node[p].left].count; if (cot >= k) { return query(node[p].left, node[q].left, l, m, k); } return query(node[p].right, node[q].right, m + 1, r, k - cot); } int main() { ll n, q; while(~scanf("%lld%lld",&n,&q)) { ha.clear(); tot = 0; for(ll i = 1; i <= n; i ++) { scanf("%lld", &a[i]); ha.push_back(a[i]); } sort(ha.begin(), ha.end()); ha.erase(unique(ha.begin(), ha.end()), ha.end()); ll m = ha.size(); null = newnode(0, 0, 0); root[0] = newnode(0, 0, 0); for(ll i = 1; i <= n; i ++) { a[i] = lower_bound(ha.begin(), ha.end(), a[i]) - ha.begin(); root[i] = ins(root[i - 1], 0, m - 1, a[i]); } while(q--) { ll l, r, k; scanf("%lld%lld%lld", &l, &r, &k); printf("%lld\n",query(root[l - 1], root[r], 0, m - 1, k)); } } return 0; }主席树模板题(2019杭电多校2) HDU 6601
