描述

• 給定一個長度為N的已知序列A[i](1<=i<=N)，要求維護(hù)這個序列，能夠支持以下兩種操作：
• 1、查詢A[i],A[i+1],A[i+2],...,A[j](1<=i<=j<=N)中，升序排列后排名第k的數(shù)。
• 2、修改A[i]的值為j。

分析

• 用了很長時間理解樹狀數(shù)組+主席樹的做法
• 這里先有一個正常的主席樹, 保存無修改時的數(shù)據(jù), 然后用樹狀數(shù)組維護(hù)一個記錄增量的主席樹, 維護(hù)的信息和普通樹狀數(shù)組一樣, 也是是某一段內(nèi)的數(shù)據(jù). 比如修改了位置x的數(shù)據(jù), 那么需要更新 x, x+lowbit(x)... 直到剛小于n 的數(shù)據(jù)

#include #include #include #include using namespace std;const int maxnode = 3000000; const int maxn = 60000 + 10; const int maxm = 10000 + 10;struct Question {int a, b, c, k; } qst[maxm];int label; int A[maxn], T[maxn]; int root[maxn<<1]; int s[maxnode], lc[maxnode], rc[maxnode];#define q qst[i] #define M (L+R>>1)void build(int& x, int y, int L, int R, int v) {x = ++label;lc[x] = lc[y], rc[x] = rc[y], s[x] = s[y] + 1;if(L == R) return;if(v <= M) build(lc[x], lc[y], L, M, v);else build(rc[x], rc[y], M+1, R, v); }void modify(int& x, int L, int R, int v, int d) {if(!x) x = ++label;s[x] += d;if(L == R) return;if(v <= M) modify(lc[x], L, M, v, d);else modify(rc[x], M+1, R, v, d); }int main() {freopen("dynrank.in", "r", stdin);freopen("dynrank.out", "w", stdout);int kase;scanf("%d", &kase);while(kase--) {label = 0;int n, m, tot = 0;scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++) {scanf("%d", &A[i]);T[++tot] = A[i];}char opt[2];for(int i = 1; i <= m; i++) {scanf("%s", opt);if(opt[0] == 'Q') {q.k = 0;scanf("%d %d %d", &q.a, &q.b, &q.c);} else {q.k = 1;scanf("%d %d", &q.a, &q.b);T[++tot] = q.b;}}sort(T+1, T+tot+1);tot = unique(T+1, T+tot+1)-T-1;for(int i = 1; i <= n; i++)A[i] = lower_bound(T+1, T+tot+1, A[i])-T;// 幾個 memset 特別耗費(fèi)時間, 可以巧妙地?fù)Q掉 memset(root, 0, sizeof(root));memset(s, 0, sizeof(s));memset(lc, 0, sizeof(lc));memset(rc, 0, sizeof(rc));// 原始主席樹占用空間 [n+1, n+n], 記錄前綴和// 記錄增量占用空間 [1, n], 記錄某個位置的增量for(int i = 1; i <= n; i++)build(root[i + n], root[i-1 + n], 1, tot, A[i]);for(int i = 1; i <= m; i++)if(q.k == 0) {vectorq1, q2; int L = 1, R = tot, rk = q.c; // 答案區(qū)間 [L, R] if(q.a == 1) q1.push_back(root[0]); else q1.push_back(root[q.a-1 + n]); q2.push_back(root[q.b + n]); for(int x = q.a-1; x > 0; x -= (x&-x)) q1.push_back(root[x]); for(int x = q.b; x > 0; x -= (x&-x)) q2.push_back(root[x]); while(L < R) { int ls = 0; for(int x = 0; x < q1.size(); x++) ls -= s[lc[q1[x]]]; for(int x = 0; x < q2.size(); x++) ls += s[lc[q2[x]]]; if(rk <= ls) { for(int x = 0; x < q1.size(); x++) q1[x] = lc[q1[x]]; for(int x = 0; x < q2.size(); x++) q2[x] = lc[q2[x]]; R = M; } else { for(int x = 0; x < q1.size(); x++) q1[x] = rc[q1[x]]; for(int x = 0; x < q2.size(); x++) q2[x] = rc[q2[x]]; L = M + 1, rk -= ls; } } printf("%d\n", T[L]); } else { for(int x = q.a; x <= n; x += (x&-x)) modify(root[x], 1, tot, A[q.a], -1); A[q.a] = lower_bound(T+1, T+tot+1, q.b)-T; for(int x = q.a; x <= n; x += (x&-x)) modify(root[x], 1, tot, A[q.a], 1); } } return 0; }

總結(jié)

以上是生活随笔為你收集整理的COGS-257-动态排名系统-树状数组+主席树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。