主席树
周五晚蔡大神讲了下，觉得不是很难的东西，然后就可是敲，发现好像就是个持久化线段树（？！）
当晚笔记：
主席树，其实就是多棵可持久化权值线段树
那什么是可持久化线段树呢？
如树1中就在子树i，树2中也存在长的一毛一样的子树i’,那么我们完全不用建两棵相同的子树啊，直接树1子节点是i，树2的子节点也是i……（这样还是树么orz）
何为主席树，
比如数列【2，3，1，6，4，5】
那么权值为【1-6】
然后一树以包括【2】建一棵权值线段树
二树以包括【2，3】建一棵权值线段树
三树以包括【2，3，1】建一棵权值线段树
。。。。。。
六树以包括【2，3，1，6，4，5】建一棵权值线段树。
可以发现要建好多棵线段树，还可以发现树i是在树i-1的基础上建的。（这用于以后的修改，先不说）
然后我们来研究下这些树的性质：
比如在统计【l,r】中大于y的点有多少个。
发现树r的信息减掉树l-1的信息，然后就可以得到【l,r】的信息（也可以看成一棵【l,r】的权值线段树）
至于修改，前面说了，只是在前一个基础上改罢了
修改操作：简单说就是左树不一样那么就左树改右树还是老树……
procedure insert(x,ll,rr,old:longint;var new:longint); var mid:longint; begin inc(tot); new:=tot; sum[new]:=sum[old]+1; if ll=rr then exit; mid:=(ll+rr)>>1; if x<=mid then begin right[new]:=right[old]; insert(x,ll,mid,left[old],left[new]); end else begin left[new]:=left[old]; insert(x,mid+1,rr,right[old],right[new]); end; end;
要是碰到修改怎么办……
如果从左到右重建，就要修改好多棵线段树。但是发现树i保存的是【1，i】的信息，这东西不就是信息的前缀和？前缀和在单点修改时有个神器bit，使修改n询问1变为修改logn询问logn。
单点修改
procedure add(x,y,z:longint); begin while x<=n do begin change(y,z,1,total,root[x],root[x]); inc(x,lowbit(x)); end; end;
把insert稍微改装一下变成change，多了个参数y，当是删除时y=-1，加是y=1.（其实就是bit套主席树而已啦）
然后区间的还没写过。
然后主席树各种速度碾压好可怕。
然后我的主席树好像写的很丑？
最后是题目汇总：
1901: Zju2112 Dynamic Rankings
3524: [Poi2014]Couriers
3207: 花神的嘲讽计划Ⅰ
2653: middle
3439: Kpm的MC密码（略欢乐，倒建trie似乎在usaco就见过，还有出题人提供的题解有很强的误导向，他是专门写复杂来吓我们的！然后小问题调了好久）