[luoguP2617] Dynamic Ranking（树状数组 套 主席树 + 离散化）

传送门

BZOJ上是权限题，洛谷赞啊。

求区间 K 大数很简单。

但是如果修改某个数的话，那么就得把这个数及后面所建的主席树都更新一遍 nlogn，显然不行。

所以可以在外面套一个树状数组来优化，树状数组的每一个节点都表示某个区间的主席树。

所以可以通过树状数组来求前缀和主席树。

具体实现看代码。

——代码

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 5 const int MAXN = 20005; 6 int n, m, tot, cnt, size, t1, t2; 7 int a[MAXN], b[MAXN], x[MAXN], y[MAXN], z[MAXN], q1[MAXN], q2[MAXN], root[MAXN], ls[MAXN * 100], rs[MAXN * 100], sum[MAXN * 100]; 8 char s[MAXN]; 9 10 inline int read() 11 18 19 inline void insert(int &now, int l, int r, int x, int v) 20 28 29 inline int query(int l, int r, int x) 30 41 else 42 47 } 48 49 int main() 50 61 62 std::sort(b + 1, b + tot + 1); size = std::unique(b + 1, b + tot + 1) (b + 1); 64 for(i = 1; i <= n; i++) a[i] = std::lower_bound(b + 1, b + size + 1, a[i]) b; 65 for(i = 1; i <= m; i++) 66 if(s[i] == 'C') 67 z[i] = std::lower_bound(b + 1, b + size + 1, z[i]) b; 68 69 for(i = 1; i <= n; i++) 70 for(j = i; j <= size; j += j & j) 71 insert(root[j], 1, size, a[i], 1); 72 73 for(i = 1; i <= m; i++) 74 if(s[i] == 'Q') 75 81 else 82 87 return 0; 88 }
View Code

上一篇：[BZOJ1264][AHOI2006]基因匹配Match（DP + 树状数组）

下一篇：[TyvjP1313] [NOIP2010初赛]烽火传递（单调队列 + DP）

---

stl 主席树 树状数组 离散化 树套树