【模板】可持久化数组（可持久化线段树/平衡树）-白红宇

【模板】可持久化数组（可持久化线段树/平衡树）

阅读量：4709 次

发布时间：2019-06-10

本文共 2650 字，大约阅读时间需要 8 分钟。

题目背景

UPDATE : 最后一个点时间空间已经放大

标题即题意

有了可持久化数组，便可以实现很多衍生的可持久化功能（例如：可持久化并查集）

题目描述

如题，你需要维护这样的一个长度为

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

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

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

输入输出格式

输入格式：

输入的第一行包含两个正整数

第二行包含 $a_i ai，1≤i≤N 1 \leq i \leq N 1≤i≤N）。$

接下来

对于操作1，格式为 $v_i \ 1 \ {loc}_i \ {value}_i vi 1 loci valuei，即为在版本vi v_i vi的基础上，将 aloci a_{$
{loc}_i} ${value}_i valuei$

对于操作2，格式为 $v_i \ 2 \ {loc}_i vi 2 loci，即访问版本vi v_i vi中的 aloci a_{ {loc}_i} aloci的值$

输出格式：

输出包含若干行，依次为每个操作2的结果。

输入输出样例

输入样例#1：

5 1059 46 14 87 410 2 10 1 1 140 1 1 570 1 1 884 2 40 2 50 2 44 2 12 2 21 1 5 91

输出样例#1：

598741878846

说明

数据规模：

对于30%的数据： $\leq N, M \leq {10}^3 1≤N,M≤103$

对于50%的数据： $\leq N, M \leq {10}^4 1≤N,M≤104$

对于70%的数据： $\leq N, M \leq {10}^5 1≤N,M≤105$

对于100%的数据： $\leq N, M \leq {10}^6, 1 \leq {loc}_i \leq N, 0 \leq v_i < i, -{10}^9 \leq a_i, {value}_i \leq {10}^91≤N,M≤106,1≤loci≤N,0≤vi<i,−109≤ai,valuei≤109$

经测试，正常常数的可持久化数组可以通过，请各位放心

~~数据略微凶残，请注意常数不要过大~~

~~另，此题I/O量较大，如果实在TLE请注意I/O优化~~

样例说明：

一共11个版本，编号从0-10，依次为：

0 : 59 46 14 87 41

1 : 59 46 14 87 41

2 : 14 46 14 87 41

3 : 57 46 14 87 41

4 : 88 46 14 87 41

5 : 88 46 14 87 41

6 : 59 46 14 87 41

7 : 59 46 14 87 41

8 : 88 46 14 87 41

9 : 14 46 14 87 41

10 : 59 46 14 87 91

思路

其实就是写个可持久化线段树就行了；

会了可持久化数组，就可以进行可持久化并查集的操作了QuQ

代码实现

1 #include
      
        2 const int maxn=1e6+10; 3 int n,m; 4 int rt[maxn],ts; 5 int t[maxn<<4],ls[maxn<<4],rs[maxn<<4]; 6 void build(int&k,int l,int r){ 7     k=++ts; 8     if(l==r){ 9         scanf("%d",&t[k]);10         return;11     }12     int mid=l+r>>1;13     build(ls[k],l,mid);14     build(rs[k],mid+1,r);15 }16 void change(int q,int&p,int l,int r,int x){17     p=++ts;18     if(l==r){19         scanf("%d",&t[p]);20         return;21     }22     int mid=l+r>>1;23     if(x<=mid) change(ls[q],ls[p],l,mid,x),rs[p]=rs[q];24     else change(rs[q],rs[p],mid+1,r,x),ls[p]=ls[q];25 }26 int search(int p,int l,int r,int x){27     if(l==r) return t[p];28     int mid=l+r>>1;29     if(x<=mid) return search(ls[p],l,mid,x);30     else return search(rs[p],mid+1,r,x);31 }32 int main(){33     scanf("%d%d",&n,&m);34     build(rt[0],1,n);35     int id,opt,l;36     for(int i=1;i<=m;i++){37         scanf("%d%d%d",&id,&opt,&l);38         if(opt==1) change(rt[id],rt[i],1,n,l);39         else printf("%d\n",search(rt[id],1,n,l)),rt[i]=rt[id];40     }41     return 0;42 }

转载于:https://www.cnblogs.com/J-william/p/8136005.html

你可能感兴趣的文章

Linux 中/etc/profile、~/.bash_profile 环境变量配置及执行过程