洛谷P3919 【模板】可持久化线段树 1（可持久化数组）题解

题意：如题，你需要维护这样的一个长度为 NN 的数组，支持如下几种操作

在某个历史版本上修改某一个位置上的值

访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

解法一、主席树

注意到历史版本+单点修改，容易想到可持久化线段树

和区间 $k$ 小值稍微有些不同

时间复杂度 $O(n\log n)$

本题的数据有点极限，我的写法开 long long会挂 😓

代码如下

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+25)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e6+5)
int n,Q;
int a[N],T[N],tot;
struct node
{
    int ch[2],num;
}t[N<<5];
#define ls(at) t[at].ch[0]
#define rs(at) t[at].ch[1]
int build(int l,int r)
{
    int at=++tot,mid=(l+r)>>1;
    if(l==r){t[at].num=a[l];return at;}
    ls(at)=build(l,mid);
    rs(at)=build(mid+1,r);
    return at;
}
int update(int pre,int l,int r,int x,int v)
{
    int at=++tot,mid=(l+r)>>1;
    t[at]=t[pre];
    if(l==r)
    {
        t[at].num=v;
        return at;
    }
    if(x<=mid)ls(at)=update(ls(pre),l,mid,x,v);
    else rs(at)=update(rs(pre),mid+1,r,x,v);
    return at;
}
int query(int at,int l,int r,int x)
{
    if(l==r)return t[at].num;
    int mid=(l+r)>>1;
    if(x<=mid)return query(ls(at),l,mid,x);
    else return query(rs(at),mid+1,r,x);
}
signed main()
{
    read(n);read(Q);
    for(int i=1; i<=n; i++)
        read(a[i]);
    T[0]=build(1,n);
    for(int i=1; i<=Q; i++)
    {
        int rt,op,x,y;
        read(rt);read(op);read(x);
        if(op==1)
        {
            read(y);
            T[i]=update(T[rt],1,n,x,y);
        }else
        {
            write(query(T[rt],1,n,x));
            pc('\n');T[i]=T[rt];
        }
    }
    return 0;
}

解法二、建树

这个解法是luogu题解区的Elegia神仙提出的

具体地，注意到每次修改都依赖于先前的版本

考虑建立关系树，离线处理修改操作

对于每个询问，直接记录答案，对于每个修改，则临时修改，然后dfs完恢复

不难看出这个解法可以看出有两个前提

不强制在线
修改操作可逆

显然这题满足

时间复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+25)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e6+5)
int n,Q;
int a[N],op[N],k[N],x[N],ans[N];
vector<int>vec[N];
void dfs(int u)
{
    if(op[u]==2)
    {
        ans[u]=a[k[u]];
        for(int v:vec[u])dfs(v);
    }else
    {
        swap(a[k[u]],x[u]);
        for(int v:vec[u])dfs(v);
        swap(a[k[u]],x[u]);
    }
}
signed main()
{
    read(n);read(Q);
    for(int i=1; i<=n; i++)
        read(a[i]);
    op[0]=2;
    for(int i=1; i<=Q; i++)
    {
        int rt;
        read(rt);read(op[i]);read(k[i]);
        if(op[i]==1)
            read(x[i]);
        vec[rt].push_back(i);
    }
    dfs(0);
    for(int i=1; i<=Q; i++)
        if(op[i]==2)
            write(ans[i]),pc('\n');
    return 0;
}