起因是16长春CCPC遇到了一个全场万人过的主席树题目，然而我不会orz，哭哭 可持久化线段树的本质是很多棵形态完全相同的线段树。 也可以理解成是，保存了不同时刻版本的线段树的数据结构。 如果没有可持久化线段树，那么我们如果需要不同时刻的线段树，无脑的做法可能是，需要多少个时刻的线段树，就建多少棵线段树。 但是空间绝对gg，我们考虑每次修改，其实对于一次修改，线段树上只有很少一部分被修改了，其他部分都一样。 因此，我们很容易想到，我们何不只考虑修改的部分，其他部分共用，以减少时间和空间消耗呢？ * 可持久化线段树是利用函数式编程的思想，对记录的数据只赋值不修改，每次插入一个数据后保存一个历史版本，然后利用线段树的结构完全相同，可以 …

题目链接 题意： 给定一个序列 n，有 m次查询，每次查询一个区间[l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。 思路： 先分解一下问题，我们要求一段区间位置的中位数，其实可以分解成，求区间中不同数的个数+求区间中第k大的下标。 对于求区间中不同数的个数，离线可以随便线段树，树状数组，或者莫队也行（观察到数据范围<=2E5) 在线的话，就只能可持久化线段树了。 看到一些题解中说要倒序处理...但是之前写求区间不同数的个数，我都是倒序处理的啊？ （回想一下，当时似乎正序处理也行... 倒序处理是为了，处理到第i个的时候，第i个一定是当前后缀区间中，第一个出现的... 然后第二个问题，求区间中第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]的值，改变后，程序还能针对改 变后的a继续回答上面的问题。 Input 第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。 分别表示序列的长度和指令的个数。 第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。 接下来的m行描述每条指令 每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数 …

题意： 求区间第k大数 思路： 可持久化线段树。 其实这东西在国内更常见的名字应该是 zhu xi 树？应该是由于“中国高端数据结构领导者”的hjt比较早得引入（？推广？）而得来的。 不过之前没写什么东西都被封，写个zhu xi 树，怕是政治敏感够枪毙100回了orz 似乎也叫函数式线段树。 写个模板题练下手。学习笔记之后补。 /* *********************************************** Author :111qqz Created Time :2017年10月16日 星期一 21时51分55秒 File Name :2104.cpp …

题目链接 题意：给出n个数，然后m个询问，每个询问一个区间[l,r],问该区间中不同的数有多少个。 思路：离线处理+线段树的做法不多说了： /* *********************************************** Author :111qqz Created Time :Fri 16 Sep 2016 11:34:32 PM CST File Name :code/spoj/dquery.cpp ************************************************ */ #include <cstdio> #include <cstring> …