P3919 【模板】可持久化数组（可持久化线段树/平衡树）
标签：uil 想法 using printf 优秀 int clu space pre
P3919 【模板】可持久化数组（可持久化线段树/平衡树）
可持久化线段树
不过我对与这一道题有一个想法：
有没有一种可持久化的数组？
带着类似于可持久化线段树的新建节点的想法，我画下了图：
偶们得到了一个初始数组！
接下来修改：pos 1 val 14
那么我们这么做：
这样其实我们就可以On修改On查询了！
（那么优秀的O(n2)算法，怎么能不爆踩呢）
思考了一下，这个东西好像可以分块，类似这样：
修改都在块内进行，维护一下，可以On√n?
没实现，那位大佬发表一下集训队论文吧
接下来说正经的：
这道题就是一个裸的可持久化线段树
具体网上学
记住这题的ask操作也要生成一个版本，生成一个和他ask版本一毛一样的版本！
（我正纳闷：哪来10个版本！）
代码：
#includeusing namespace std;
const int N=1000005;
struct node{
int l;
int r;
int lson;
int rson;
int val;
};
int n,m;
int a[N];
struct Sugment_Tree{
#define mid (l+r)/2
#define il inline
int root[N];
node t[N4];
int cnt;//线段树节点数
int times;//几次版本
Sugment_Tree(){cnt=0,times=0;memset(root,0,sizeof(root));}
il int build(int l,int r){
if(l==r){
cnt++;
t[cnt].val=a[l];
t[cnt].lson=-1;
t[cnt].rson=-1;
t[cnt].l=l;
t[cnt].r=r;
return cnt;
}
cnt++;
int y=cnt;
t[y].lson=build(l,mid);
t[y].rson=build(mid+1,r);
t[y].val=0;
t[y].l=l;
t[y].r=r;
return y;
}
il int upt(node u,int pos,int X){
if(u.l==u.r&&u.r==pos){
cnt++;
t[cnt]=u;
t[cnt].val=X;
return cnt;
}
cnt++;
int y=cnt;
t[y]=u;
node l=t[u.lson],r=t[u.rson];
if(l.l=pos){
t[y].lson=upt(l,pos,X);
t[y].rson=u.rson;
}
if(r.l=pos){
t[y].rson=upt(r,pos,X);
t[y].lson=u.lson;
}
return y;
}
il int serch(node u,int pos){
if(u.l==u.r&&u.r==pos){
return u.val;
}
node l=t[u.lson],r=t[u.rson];
if(l.l=pos){
return serch(l,pos);
}
if(r.l=pos){
return serch(r,pos);
}
return -10;
}
}T;
int main(){
freopen("a.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i"%d",&a[i]);
T.times++;
T.root[1]=T.build(1,n);
while(m--){
int a,b,c,d;
scanf("%d%d%d",&a,&b,&c);
a++;
if(b==1){
scanf("%d",&d);
T.times++;
T.root[T.times]=T.upt(T.t[T.root[a]],c,d);
}
else{
printf("%d\n",T.serch(T.t[T.root[a]],c));
T.times++;
T.root[T.times]=T.root[a];
}
}
return 0;
}
P3919 【模板】可持久化数组（可持久化线段树/平衡树）
标签：uil 想法 using printf 优秀 int clu space pre
原文地址：https://www.cnblogs.com/QYJ060604/p/11569075.html
评论