震惊,可持久化数组竟然使用可持久化线段树维护
使用可持久化线段树维护,就只有单点修改和单点查询
然后,还有一个小坑点,就是查询时也会生成一个与所使用的历史版本一样的版本
不然只有20分
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
const int maxn=1e5+10;
int ls[maxn<<5],rs[maxn<<5],T;
int t[maxn<<5];
int root[maxn];
int base[maxn];
int read()
{
char c=getchar();
int res=0,f=1;
while(c<'0'||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while(c<='9'&&c>='0')
{
res=(res<<3)+(res<<1)+c-'0';
c=getchar();
}
return res*f;
}
void build(int l,int r,int &R)
{
R=++T;
if(l==r)
{
t[R]=base[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls[R]);
build(mid+1,r,rs[R]);
}
int refix(int R,int pos,int val,int l,int r)
{
int nxt=++T;
ls[nxt]=ls[R];
rs[nxt]=rs[R];
if(l==r)
{
t[nxt]=val;
return nxt;
}
int mid=(l+r)>>1;
if(pos<=mid)
ls[nxt]=refix(ls[R],pos,val,l,mid);
else
rs[nxt]=refix(rs[R],pos,val,mid+1,r);
return nxt;
}
int check(int R,int loc,int l,int r)
{
if(l==r)
return t[R];
int mid=(l+r)>>1;
if(loc<=mid)
return check(ls[R],loc,l,mid);
else
return check(rs[R],loc,mid+1,r);
}
int main()
{
int n=read(),m=read();
for(int i=1;i<=n;i++)
base[i]=read();
build(1,n,root[0]);
int v,opt,loc,value;
for(int i=1;i<=m;i++)
{
v=read();opt=read();loc=read();
if(opt==1)
{
value=read();
root[i]=refix(root[v],loc,value,1,n);
}
else
{
root[i]=root[v];
printf("%d
",check(root[v],loc,1,n));
}
}
return 0;
}