可持久化线段树
如果我们要维护一个可持续的，支持查询历史版本的数组该怎么做
给每一个版本建立一颗线段树？那太占空间了。
我们可以不同版本公用一些节点，对于每个版本，只把和上一个版本不一样的部分建立线段树的新节点。这样我们就有了可持久化线段树。
需要的前置知识：动态开点。
依照上面的思想，这个题只有单点修改和单点查询，很容易解决。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
struct tree{
int l;
int r;
int v;
}tr[24000006];
int cnt;
int f,x,y,z;
int n,m;
int a[10000001];
void build(int& ro,int l,int r){
ro=++cnt;
if(l==r){
tr[ro].v=a[l];
return ;
}
int mid=(l+r)>>1;
build(tr[ro].l,l,mid);
build(tr[ro].r,mid+1,r);
}
int rt[1000001];
void update(int& ro,int pre,int l,int r,int po,int k){
ro=++cnt;
tr[ro]=tr[pre];
if(l==r){
tr[ro].v=k;
return ;
}
int mid=(l+r)>>1;
if(po<=mid) update(tr[ro].l,tr[pre].l,l,mid,po,k);
else update(tr[ro].r,tr[pre].r,mid+1,r,po,k);
}
int que(int ro,int l,int r,int k){
if(l==r){
return tr[ro].v;
}
int mid=(l+r)>>1;
if(k<=mid) return que(tr[ro].l,l,mid,k);
else return que(tr[ro].r,mid+1,r,k);
}
int main(){
read(n);read(m);
for(int i=1;i<=n;++i){
read(a[i]);
}
build(rt[0],1,n);
for(int i=1;i<=m;++i){
read(x);read(f);read(y);
if(f==1){
read(z);
update(rt[i],rt[x],1,n,y,z);
}else{
printf("%d\n",que(rt[x],1,n,y));
rt[i]=rt[x];
}
}
return 0;
}
建立一颗权值线段树，按照上面的思想，每从左往右处理一个位置，就是建立一个新版本，如果要知道\([l,r]\)，那么只需要用这两个端点对应的部分相减。就可以知道区间的信息，然后线段树上二分就可以了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
int n;
int m;
struct tree{
int l;
int r;
int sum;
}tr[4800005];
int cnt;
void build(int &ro,int l,int r){
ro=++cnt;
tr[ro].sum=0;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(tr[ro].l,l,mid);
build(tr[ro].r,mid+1,r);
}
int a[1000005];
int b[1000005];
int l;
int rt[10000005];
void update(int &ro,int pre,int l,int r,int k){
ro=++cnt;
tr[ro]=tr[pre];
tr[ro].sum=tr[pre].sum+1;
if(l==r) return ;
int mid=(l+r)>>1;
if(k<=mid) update(tr[ro].l,tr[pre].l,l,mid,k);
else update(tr[ro].r,tr[pre].r,mid+1,r,k);
}
int f;
int x;
int y;
int z;
int que(int pre,int rr,int l,int r,int k){
if(l==r) return l;
int mid=tr[tr[rr].l].sum-tr[tr[pre].l].sum;
int mmid=(l+r)>>1;
if(mid>=k){
return que(tr[pre].l,tr[rr].l,l,mmid,k);
}else{
return que(tr[pre].r,tr[rr].r,mmid+1,r,k-mid);
}
}
int main(){
read(n);read(m);
for(int i=1;i<=n;++i){
read(a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
int ll=unique(b+1,b+n+1)-b-1;
build(rt[0],1,ll);
for(int i=1;i<=n;++i){
int tem=lower_bound(b+1,b+ll+1,a[i])-b;
update(rt[i],rt[i-1],1,ll,tem);
}
for(int i=1;i<=m;++i){
read(x);read(y);read(z);
printf("%d\n",b[que(rt[x-1],rt[y],1,ll,z)]);
}
return 0;
}