这个比splay好学多了(
主席树就是把每次修改的版本保留下来，版本就是线段树曾经的一个状态。
如果打暴力的话可以想把每个状态的线段树都保留下来，炸飞了。
主席树单点修改的话就是发现了每次修改只改了包含这个点的层，线段树上，这是 \(\log n\) 级的，我们可以只创建这些新节点。每次修改我们就重新设置一个根，这个根只领导了 \(\log\) 的新节点，其他的都连接到原树上不被修改的点。
图：
这个新的链顶就是新的一个根，这个链可以访问到一个完整的常规的线段树，和原本的根（好比说是1吧），是一样的。
时间和空间复杂度都是 \(O(n\log n)\) 级别
可持久化线段树1
#include<bits/stdc++.h>
typedef int count ;
typedef long long value;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cout<<"###"<<x<<std::endl;
#define maxn 1000010
count n,m,all;
count rt[maxn];
value a[maxn];
struct tree{
count l,r,ls,rs;
count data;
} shu[maxn<<5];
inline void add(count &hao){
if(!hao){
hao=++all;
}
}
inline void copy(count &hao){
shu[++all]=shu[hao];
hao=all;
}
inline void pushup(count hao){
shu[hao].data=shu[shu[hao].ls].data+shu[shu[hao].rs].data;
}
void bt(count &hao,count l,count r){
add(hao);
shu[hao].l=l,shu[hao].r=r;
if(l==r){
shu[hao].data=a[l];
return ;
}
count mid=(l+r)>>1;
bt(shu[hao].ls,l,mid);
bt(shu[hao].rs,mid+1,r);
pushup(hao);
}
void update(count &hao,count pos,count val){
copy(hao);
if(shu[hao].l==shu[hao].r){
shu[hao].data=val;
return ;
}
count mid=(shu[hao].l+shu[hao].r)>>1;
if(pos<=mid) update(shu[hao].ls,pos,val);
else update(shu[hao].rs,pos,val);
pushup(hao);
}
value ask(count hao,count pos){
if(!hao) return 0;
if(shu[hao].l==shu[hao].r){
return shu[hao].data;
}
count mid=(shu[hao].l+shu[hao].r)>>1;
value val=0;
if(pos<=mid) val+=ask(shu[hao].ls,pos);
else val+=ask(shu[hao].rs,pos);
return val;
}
int main(){
n=read(),m=read();
for(count i=1;i<=n;i++){
a[i]=read();
}
bt(rt[0],1,n);
for(count i=1;i<=m;i++){
count ver=read();
count op=read();
if(op==1){
count pos=read(),val=read();
rt[i]=rt[ver];
update(rt[i],pos,val);
}
else{
count pos=read();
write(ask(rt[ver],pos)),putchar('\n');
rt[i]=rt[ver];
}
}
return 0;
}
经典问题：查 \([l,r]\) 中第 \(k\) 小。
前缀和+权值线段树。
查 \(l-1\) 和 \(r\) 版本的权值线段树，维护同一值域的部分可以相加减，差即为这一区间的信息。剩下按权值线段树常规做就行。
可持久化线段树2
#include<bits/stdc++.h>
typedef int count ;
typedef long long value;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cout<<"###"<<x<<std::endl;
#define maxn 200010
count n,m;
value a[maxn],book[maxn];
count rt[maxn],all;
struct tree{
count data;
count l,r,ls,rs;
} shu[maxn<<5];
inline void add(count &k){
if(!k){
k=++all;
}
}
inline void copy(count &k){
shu[++all]=shu[k];
k=all;
}
inline void pushup(count hao){
shu[hao].data=(shu[shu[hao].ls].data+shu[shu[hao].rs].data);
}
void insert(count &hao,count l,count r,count pos){
copy(hao);
shu[hao].l=l,shu[hao].r=r;
if(l==r){
shu[hao].data++;
return ;
}
count mid=(l+r)>>1;
if(pos<=mid) insert(shu[hao].ls,l,mid,pos);
else insert(shu[hao].rs,mid+1,r,pos);
pushup(hao);
}
value ask(count hao1,count hao2,count k){
if(shu[hao1].l==shu[hao1].r) return shu[hao1].l;
count x=shu[shu[hao1].ls].data-shu[shu[hao2].ls].data;
if(k<=x){
return ask(shu[hao1].ls,shu[hao2].ls,k);
}
else{
return ask(shu[hao1].rs,shu[hao2].rs,k-x);
}
}
int main(){
n=read(),m=read();
for(count i=1;i<=n;i++){
a[i]=read();
book[i]=a[i];
}
std::sort(book+1,book+1+n);
count cnt=std::unique(book+1,book+1+n)-book-1;
for(count i=1;i<=n;i++){
count zhen=std::lower_bound(book+1,book+1+cnt,a[i])-book;
rt[i]=rt[i-1];
insert(rt[i],1,n,zhen);
}
for(count i=1;i<=m;i++){
count l=read(),r=read(),k=read();
write(book[ask(rt[r],rt[l-1],k)]),putchar('\n');
}
return 0;
}
这个套路主要应用于值域和位置区间都有限制的情景，非常好算法，英雄联盟。
比如：P3923 美味
以后看到位运算的题一定要按位考虑?
按位考虑，类似树上最长异或路径。二进制下，确定了 \(b_i\) 的第 \(k\) 位，我们尽量让 \(a_j+x_i\) 的这一位不一样。然后和那个题一样从最高位到最低位贪心，把当前答案 \(ans\) 记下来，把 \(a_j+x_i\) 看做一个整体，查的都是减去了 \(x_i\) 的，也就是查 \([ans-x_i,ans-x_i+(1<<k)-1]\)（为的是保证这一位是我们想要的数）区间有没有数。查 \([l,r]\) 位置这个值域之内的数，正好专业对口。
好题
疯狂的颜色序列
比较板子。直接想莫队做法，按位置建树，每出现一个颜色就把这个颜色上次出现的位置的贡献减掉，实现只维护最新位置的某个颜色。对 \(r\) 的版本进行常规区间查询就好。
(实心三角)疯狂的颜色序列
To be continue......maybe