维护一个长度为 $n$ 的数组,要求实现以下两个操作:

1.修改某一个版本上某个单点的值。

2.查询某一个版本上某个单点的值。

操作共 $m$ 次,每次操作后生成一个新的版本,版本号从 1 开始,初始版本编号为 0。

$1\leq n,m\leq 10^6$。


因为是维护数列的题目,所以先建立一棵普普通通的线段树。

image.png

如果我们要修改 10 号节点对应位置的值。最暴力的是重新建立一棵线段树。正确性自然不用说,但是时间上就爆炸了。

观察单点修改其实并没有影响全部节点。10 号节点的祖先也只有 5,2 和 1 号。所以考虑如下图一样修改。(红色为新增节点)

image.png

很明显,新增节点不会超过 $\log$ 级别。所以这个操作是 $O(\log n)$ 的时间复杂度。

如何实现呢?根节点当然是要新建一个。每次选择左右节点的时候,如果某个子节点的区间没有被修改操作所影响,那么直接把这个节点直接连到新的节点上。

比如走到 $(2')$ 这个节点时,发现 4 节点没有被修改,那么就直接把 4 接到 $(2')$ 的左儿子处,再新建一个 $(5')$ 往下走即可。

至于查询生成的新版本,一个节点都没有影响到,为了区分,只需要新建一个根节点,再把左右儿子连到上一个版本的左右儿子就行了。

对于每个版本记录一个根节点 $rt[i]$,查询这个版本的时候就从这个根节点往下即可。

代码如下。

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1e6+10;
int rt[N];
struct node
{
    int l,r;
    int w;
}t[N*20];
int cnt=0;
inline int read()
{
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
inline void build(int &k,int l,int r)
{
    ri m;
    k=++cnt;
    if(l!=r)
    {
        m=(l+r)>>1;
        build(t[k].l,l,m);
        build(t[k].r,m+1,r);
    }
    else t[cnt].w=read();
    //写k一样但是效率不如cnt 
    return;
}
inline void add(int *k,int u,int l,int r,int x)//在版本u基础上把位置x重新赋值 
{
    while(l!=r)
    {
        *k=++cnt;
        int m=(l+r)>>1;
        if(x<=m)r=m,t[*k].r=t[u].r,k=&t[*k].l,u=t[u].l;//x在左边,右边直接连到原始版本 
        else  l=m+1,t[*k].l=t[u].l,k=&t[*k].r,u=t[u].r;//x在右边,左边直接连到原始版本 
    }
    *k=++cnt;//走到x,分配新编号,读入 
    t[*k].w=read();
}
inline int ask(int k,int l,int r,int x)
{
    ri m;
    while(l!=r)
    {
        m=(l+r)>>1;
        if(x<=m)r=m,k=t[k].l;
        else l=m+1,k=t[k].r;
    }
    return t[k].w;
}
int main()
{
    int n,m;
    cin>>n>>m;
    int v,op,loc;
    build(rt[0],1,n);
    for(ri i=1;i<=m;i++)//处理第i个历史版本 
    {
        v=read(),op=read(),loc=read();
        if(op==1)
            add(&rt[i],rt[v],1,n,loc);
        else
        {
            printf("%d\n",ask(rt[v],1,n,loc));
            rt[i]=++cnt;
            t[rt[i]].l=t[rt[v]].l;
            t[rt[i]].r=t[rt[v]].r;
            //直接连到版本v上去 
        }
    }
    return 0;
}
最后修改:2021 年 08 月 16 日
如果觉得我的文章对你有用,请随意赞赏