P2617 Dynamic Rankings[带修主席树(模板)]

$Dynamic Rankings$

给出一个长度为 $N$ 的数列 $A_i$, 要求支持

• 区间查询第 $K$ 大 .
• 单点修改 .

$N le 10^5$

---

普通主席树是使用每个位置 (设为$i$) 重建一颗 权值线段树, 每颗线段树包含 $[1, i]$ 的信息, 再用动态开点的方法充分利用线段树间重复信息, 以 $O(NlogN)$ 的时空复杂度, 将 前缀和 操作应用到 权值线段树 之间, 实现 静态区间查询第 $K$ 大 .

---

带修主席树的作用顾名思义, 支持 动态查询区间第 $K$ 大 .

动态地对前缀和进行修改, 可以使用树状数组,
树状数组 每个节点保存 一个权值线段树 的根节点编号,
这里放出树状数组的图示,

每个权值线段树保存的不再是 $[1, i]$ 的信息了, 保存的是什么呢?

举个例子,
图中编号为 $1,3,5,7$ 的节点分别保存了 $1,3,5,7$ 单点的信息,
图中编号为 $2$ 保存的是 $[1, 2]$ 的信息,
编号为 $6$ 的点保存 $[5, 6]$ 的信息
$.$
$.$
$.$
以此类推 .

所以此时 $rot[i]$ 表示的 权值线段树 保存的不再是 $[1, i]$ 的信息, 而是 $i$ 在树状数组中代表的区间的信息 .

---

注意查询时不能单独提出 $rot[r]$ 和 $rot[l-1]$ 进行递归查询,
因为这样向下递归调用儿子时仅能调动 $rot[r]$ 和 $rot[l-1]$ 的儿子, 无法代表整个 $查询区间$,

$正确的做法$ 是 事先提出所有的关于 $查询区间$ 的树状数组节点, 在往儿子节点递归的同时, $O(logn)$ 将现有的 $代表父亲$ 的 树状数组节点 转化为 $代表儿子节点$, 保证 $查询区间$ 的完整性 .

---

一共要加入 主席树 $N$ 个节点, 每次加入要修改 $logN$ 个树状数组节点, 每个树状数组节点需要 往下递归修改 $O(logN)$ 个,
所以 $时空复杂度$ $O(nlog^2n)$ .

---

$color{red}{注意 cnt_a 与 cnt_b 的清空.}$
$color{red}{注意离散数组B[]要开2倍,因为B处理原数列的同时还要处理修改时新出现的值.}$

#include<bits/stdc++.h>
#define reg register

const int maxn = 1e5 + 5;

int N;
int M;
int Len;
int cnt_a;
int cnt_b;
int A[maxn];
int B[maxn<<1];
int A1[maxn];
int B1[maxn];
int rot[maxn];

namespace President_Tree{

        struct Node{ int sum, lt, rt; } T[maxn*400]; 
        int node_cnt = 0;

        void Add(int &k, int l, int r, int aim, int opt){
                if(!k) k = ++ node_cnt;
                T[k].sum += opt;
                if(l == r) return ;
                int mid = l+r >> 1;
                if(aim <= mid) Add(T[k].lt, l, mid, aim, opt);
                else Add(T[k].rt, mid+1, r, aim, opt);
        }

        int Query(int l, int r, int aim){
                if(l == r) return l;
                int sum = 0;
                for(reg int i = 1; i <= cnt_b; i ++) sum += T[T[B1[i]].lt].sum;
                for(reg int i = 1; i <= cnt_a; i ++) sum -= T[T[A1[i]].lt].sum;
                int mid = l+r >> 1;
                if(aim <= sum){
                        for(reg int i = 1; i <= cnt_b; i ++) B1[i] = T[B1[i]].lt;
                        for(reg int i = 1; i <= cnt_a; i ++) A1[i] = T[A1[i]].lt;
                        return Query(l, mid, aim);
                } 
                for(reg int i = 1; i <= cnt_b; i ++) B1[i] = T[B1[i]].rt;
                for(reg int i = 1; i <= cnt_a; i ++) A1[i] = T[A1[i]].rt;
                return Query(mid+1, r, aim-sum);
        }

}

struct Que{ int opt, l, r, k, pos, to; } Q[maxn];

int main(){
        scanf("%d%d", &N, &M);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]), B[i] = A[i];
        int cnt = N;
        for(reg int i = 1; i <= M; i ++){
                char s[3];
                scanf("%s", s);
                if(s[0] == 'Q') Q[i].opt = 1, scanf("%d%d%d", &Q[i].l, &Q[i].r, &Q[i].k);
                else Q[i].opt = 0, scanf("%d%d", &Q[i].pos, &Q[i].to), B[++ cnt] = Q[i].to;
        }
        std::sort(B+1, B+cnt+1); Len = std::unique(B+1, B+cnt+1) -B-1;
        for(reg int i = 1; i <= N; i ++){
 		       	A[i] = std::lower_bound(B+1, B+Len+1, A[i]) - B;
                int t = i;
                while(t <= N) President_Tree::Add(rot[t], 1, Len, A[i], 1), t += t&-t;
    	}
    	
        for(reg int i = 1; i <= M; i ++){
                if(Q[i].opt == 1){
                	cnt_b = cnt_a = 0;
                	int t = Q[i].r;
                	while(t >= 1) B1[++ cnt_b] = rot[t], t -= t&-t;
                    t = Q[i].l - 1;
                	while(t >= 1) A1[++ cnt_a] = rot[t], t -= t&-t;
            		printf("%d
", B[President_Tree::Query(1, Len, Q[i].k)]);
	        	}
                else{
                        int t = Q[i].pos;
                        while(t <= N) President_Tree::Add(rot[t], 1, Len, A[Q[i].pos], -1), t += t&-t;
                        A[Q[i].pos] = std::lower_bound(B+1, B+Len+1, Q[i].to) - B, t = Q[i].pos; 
                        while(t <= N) President_Tree::Add(rot[t], 1, Len, A[Q[i].pos], 1), t += t&-t;
                }
        }
        return 0;
}