起因是16长春CCPC遇到了一个全场万人过的主席树题目，然而我不会orz，哭哭

可持久化线段树的本质是很多棵形态完全相同的线段树。

也可以理解成是，保存了不同时刻版本的线段树的数据结构。

题目链接

题意：

给定一个序列 n，有 m次查询，每次查询一个区间[l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。

思路：

先分解一下问题，我们要求一段区间位置的中位数，其实可以分解成，求区间中不同数的个数+求区间中第k大的下标。

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1

],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改

题意：

求区间第k大数

思路：

可持久化线段树。

其实这东西在国内更常见的名字应该是 zhu xi 树？应该是由于“中国高端数据结构领导者”的hjt比较早得引入（？推广？）而得来的。

题目链接 题意：给出n个数，然后m个询问，每个询问一个区间[l,r],问该区间中不同的数有多少个。

思路：离线处理+线段树的做法不多说了：

 1/* ***********************************************
 2Author :111qqz
 3Created Time :Fri 16 Sep 2016 11:34:32 PM CST
 4File Name :code/spoj/dquery.cpp
 5************************************************ */
 6#include <cstdio>
 7#include …