牛客周赛62F查询区间中位数
主席树的主要思想就是：保存每次插入操作时的历史版本，以便查询区间第 k 小。
1.每次操作修改节点数是一样的，只有logn个。
2.在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化了。
3.需要动态开点

求 [l,r] 区间 k 小值
1.离散化原始数组a
2.在线段树a[i]这个位置+1，即插入a[i]
3.原数组下标[l,r](这里的[l,r]指的是数组的第l个数到第r个数)区间的k小值，就是第l个版本到第r个版本的k小值。因此每次插入时记录当前版本该节点的[l,r](这里的[l,r]指的是线段树节点的包含的区间端点l,r)插入了多少个值。如此可以O(1)时间查找第l个数到第r个数，某个节点的区间内插入了多少个数。

ps.重新说明。查询[l,r]区间第k小数，等于查询第l次到第r次插入的第k小数。然后对比第r次和第l-1次所多出的节点，利用线段树查询哪个区间是第k小数所在的区间。

4.可以O(1)时间内查找左子节点插入了多少个数x，如果x大于等于k，说明目标值在左子结点的区间内，否则在右子节点区间内。递归查询即可。

查询区间中位数只需要给定k即可。

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5;  // 数据范围
int tot, n, m;
int sum[(maxn << 5) + 10], rt[maxn + 10], ls[(maxn << 5) + 10],
    rs[(maxn << 5) + 10];
int a[maxn + 10], ind[maxn + 10], len;

int getid(const int &val) {  // 离散化
  return lower_bound(ind + 1, ind + len + 1, val) - ind;
}

int build(int l, int r) {  // 建树
  int root = ++tot;
  if (l == r) return root;
  int mid = l + r >> 1;
  ls[root] = build(l, mid);
  rs[root] = build(mid + 1, r);
  return root;  // 返回该子树的根节点
}

int update(int k, int l, int r, int root) {  // 插入操作
  int dir = ++tot;
  ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1;
  if (l == r) return dir;
  int mid = l + r >> 1;
  if (k <= mid)
    ls[dir] = update(k, l, mid, ls[dir]);
  else
    rs[dir] = update(k, mid + 1, r, rs[dir]);
  return dir;
}

int query(int u, int v, int l, int r, int k) {  // 查询操作
  int mid = l + r >> 1,
      x = sum[ls[v]] - sum[ls[u]];  // 通过区间减法得到左儿子中所存储的数值个数
  if (l == r) return l;
  if (k <= x)  // 若 k 小于等于 x ，则说明第 k 小的数字存储在在左儿子中
    return query(ls[u], ls[v], l, mid, k);
  else  // 否则说明在右儿子中
    return query(rs[u], rs[v], mid + 1, r, k - x);
}

void init() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  memcpy(ind, a, sizeof ind);
  sort(ind + 1, ind + n + 1);
  len = unique(ind + 1, ind + n + 1) - ind - 1;
  rt[0] = build(1, len);
  for (int i = 1; i <= n; ++i) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}

int l, r, k;

void work() {
  while (m--) {
    scanf("%d%d", &l, &r);
    k = ((r-l)+1)/2+1;
    printf("%d\n", ind[query(rt[l - 1], rt[r], 1, len, k)]);  // 回答询问
  }
}

int main() {
  init();
  work();
  return 0;
}