POJ 2104 K-th Number——主席树

POJ 2104 K-th Number——主席树

一开始分块搞过了，但后来ac代码交上去TLE，怀疑是加强数据或者当时是运气过的，于是学了主席树，推荐这篇博客

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;int n, m, cnt;struct Node { int L, R, sum; Node () { sum = 0; }}tree[maxn*20];struct Value { int x, id; bool operator < (const Value &rhs) const { return x < rhs.x; }}value[maxn];int root[maxn], ran[maxn];void init() { cnt = 1; root[0] = 0; tree[0].L = tree[0].R = tree[0].sum = 0;}void update(int num, int &rt, int l, int r) { tree[cnt++] = tree[rt]; rt = cnt - 1; tree[rt].sum++; if (l == r) return; int mid = (l + r)>>1; if (num <= mid) update(num, tree[rt].L, l, mid); else update(num, tree[rt].R, mid + 1, r);}int query(int i, int j, int k, int l, int r) { int d = tree[tree[j].L].sum - tree[tree[i].L].sum; if (l == r) return l; int mid = (l+r)>>1; if (k <= d) return query(tree[i].L, tree[j].L, k, l, mid); else return query(tree[i].R, tree[j].R, k-d, mid + 1, r);}int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &value[i].x); value[i].id = i; } sort(value+1, value+1+n); for (int i = 1; i <= n; i++) ran[value[i].id] = i; init(); for (int i = 1; i <= n; i++) { root[i] = root[i-1]; update(ran[i], root[i], 1, n); } int left, right, k; for (int i = 1; i <= m; i++) { scanf("%d%d%d", &left, &right, &k); printf("%d\n", value[query(root[left-1], root[right], k, 1, n)].x); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。