1901. Zju2112 Dynamic Rankings 树状数组套主席树 模板

😊 | Powered By HeartFireY

Problem Analysis

草草看了一眼题目，差点以为是可持久化线段树的裸板子。于是就回顾了以下可持久化线段树和主席树的基本操作，与本题目进行对比：

可持久化线段树支持的操作是

1. 在某个历史版本上修改某一个位置上的值
2. 访问某个历史版本的某一位置上的值

主席树的作用则主要是查询区间第 k k k小的值，这是得益于其基于权值数组建立可持久化线段树的效果。因此他的每次区间更新都会产生一个新的根节点。产生新的根节点的原因是主席树利用了前缀和的思想，维护区间起点到某个节点的信息，利用满足区间可加性信息维护的性质查询区间信息。因此它只能查询静态区间信息。

那么本题目显然是属于查询动态区间第 k k k小的问题。

那么我们就需要通过一些特殊的解决方式来处理这类问题：树套树结构。

我们使用树套树的基本思想是，不同的工作交给不同的数据结构来完成：主席树仍然负责解决区间第 k k k小的问题，树状数组则负责解决区间修改的问题。

那么怎么实现呢？

我们让树状数组的每一个节点都是一棵权值线段树，并且对每棵权值线段树维护的信息都是树状数组式的累加，这样每次查询和修改都只需要对 l o g   n log\ n log n个线段树进行操作。

Accepted Code

#include 
using namespace std;

const int N = 1e4 + 10, maxn = 1000000000;


int a[N], n, m;
int root[N], lc[N > v;
        if(op == 'Q'){
            cin >> k;
            cnt1 = cnt2 = 0;
            for(int i = u - 1; i; i -= lowbit(i)) L[++cnt1] = root[i];
            for(int i = v; i; i -= lowbit(i)) R[++cnt2] = root[i];
            cout