求区间第k小 今天打多校，找了好几个板子改，还是败了，就用队友这个吧！！
/* 求区间第k小，相应的，第k大也行（主席树） */ #include<cstdio> #include<iostream> #include<sstream> #include<cstdlib> #include<cstring> #include<string> #include<climits> #include<cmath> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<set> #include<map> #define INF 0x3f3f3f3f #define eps 1e-8 #define ll long long using namespace std; const int MAXN = 200005; const int MAXM = 4000005; // maxn的20倍 int a[MAXN]; int tot; vector<int> v; struct Tree { int count; int left, right; }; int root[MAXN]; Tree node[MAXM]; int null; int newnode(int count, int left, int right) { node[tot].count=count; node[tot].left=left; node[tot].right=right; return tot++; } int inn(int rt, int l, int r, int k) { if (l <= k && k <= r) { if (l == r) { return newnode(node[rt].count + 1, 0, 0); } int m = (l + r) >> 1; return newnode(node[rt].count + 1, inn(node[rt].left, l, m, k), inn(node[rt].right, m + 1, r, k)); } return rt; } int query(int p, int q, int l, int r, int k) { if (l == r) { return v[l]; } int m = (l + r) >> 1; int 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() { int n, q; while(scanf("%d%d", &n, &q) == 2) { v.clear(); tot = 0; for(int i = 1; i <= n; i ++) { scanf("%d", &a[i]); v.push_back(a[i]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); int m = v.size(); null = newnode(0, 0, 0); root[0] = newnode(0, 0, 0); for(int i = 1; i <= n; i ++) { a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin(); root[i] = inn(root[i - 1], 0, m - 1, a[i]); } while(q--) { int l, r, k; scanf("%d%d%d", &l, &r,&k); int pos=query(root[l - 1], root[r], 0, m - 1,k); printf("%d\n",pos); } } return 0; }
