題意：
要求維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持下面三種操作：
- \(0 \, e\)：插入一個(gè)值為\(e\)的元素
- \(1 \, e\)：刪除一個(gè)值為\(e\)的元素
- \(2 \, a \, k\)：查詢比\(a\)大的數(shù)中的第\(k\)小
分析：
因?yàn)椴迦氲臄?shù)在\(10^5\)內(nèi)，所以不需要離散化。
維護(hù)一棵主席樹，每次插入或者刪除元素都新建一棵主席樹。
對于查詢操作，先查詢不超過\(a\)的元素的個(gè)數(shù)\(cnt\)，然后再查詢序列中第\(cnt+k\)小即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn = 100000 + 10;
const int maxnode = (maxn << 5);int n;int sz, root[maxn];
int lch[maxnode], rch[maxnode], sum[maxnode];int update(int pre, int L, int R, int p, int v) {int rt = ++sz;sum[rt] = sum[pre] + v;if(L < R) {int M = (L + R) / 2;if(p <= M) { rch[rt] = rch[pre]; lch[rt] = update(lch[pre], L, M, p, v); }else { lch[rt] = lch[pre]; rch[rt] = update(rch[pre], M+1, R, p, v); }}return rt;
}int Qcnt(int rt, int L, int R, int p) {if(L == R) return sum[rt];int M = (L + R) / 2;if(p <= M) return Qcnt(lch[rt], L, M, p);else return Qcnt(rch[rt], M+1, R, p);
}int Qsum(int rt, int L, int R, int p) {if(L == R) return sum[rt];int M = (L + R) / 2;if(p <= M) return Qsum(lch[rt], L, M, p);else return sum[lch[rt]] + Qsum(rch[rt], M+1, R, p);
}int kth(int rt, int L, int R, int k) {if(L == R) return L;int num = sum[lch[rt]];int M = (L + R) / 2;if(num >= k) return kth(lch[rt], L, M, k);else return kth(rch[rt], M+1, R, k-num);
}int main()
{while(scanf("%d", &n) == 1) {int cnt = 0;sz = 0;while(n--) {int op, a; scanf("%d%d", &op, &a);if(op == 0) {cnt++;root[cnt] = update(root[cnt-1], 1, maxn, a, 1);} else if(op == 1) {if(!Qcnt(root[cnt], 1, maxn, a)) puts("No Elment!");else {cnt++;root[cnt] = update(root[cnt-1], 1, maxn, a, -1);}} else {int b; scanf("%d", &b);int k = Qsum(root[cnt], 1, maxn, a);//printf("k1 = %d\n", k);k += b;//printf("k2 = %d\n", k);if(k > sum[root[cnt]]) { puts("Not Find!"); continue; }printf("%d\n", kth(root[cnt], 1, maxn, k));}}}return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/5343355.html
總結(jié)
以上是生活随笔為你收集整理的HDU 2852 KiKi's K-Number 主席树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
