前言

可持久化

可持久化，即对于每次更改，我们都期望记录它的历史信息。

进行可持久化的数据结构通常满足，在修改操作时，数据结构本身的拓扑序没有改变，即形态没有改变；

例如线段树，Trie 树，数组等都可以容易地进行可持久化。

关于主席树和可持久化线段树的区别

主席树全称是可持久化权值线段树，参见知乎讨论。

关于 $\log n$ 和 $\log_{2} n$ 的区别

在数学中（尤其是纯数学领域）， $\log n$ 通常表示以自然对数 $e$ 为底的对数，即 $\ln n$ 。

在计算机科学中， $\log n$ 通常默认表示以 $2$ 为底的对数，即 $\log_{2} n$ ，因为计算机科学中很多问题涉及二分法（如分治算法、二叉树等）。

可持久化线段树

【模板】可持久化线段树 1（可持久化数组）

非常经典的可持久化权值线段树入门题——静态区间第 $k$ 小：【模板】可持久化线段树 2

引入

给定 $n$ 个整数构成的序列 $a$ ，将对于指定的闭区间 $[l, r]$ 查询其区间内的第 $k$ 小值。

我们能想到用整体二分或者二分+分块去解决问题；

若直接建立权值线段树，发现是无法解绝问题的，考虑使用主席树，其的主要思想就是：保存权值线段树上每次插入操作时的历史版本，以便查询区间第 $k$ 小。

解析

我们分析一下，发现每次修改操作修改的点的个数是一样的，只更改了 $O (\log n)$ 个结点，形成一条链，也就是说 每次更改的结点数 等于 树的高度。

（例如下图，修改了 $[1, 8]$ 中对应权值为 $1$ 的结点，红色的点即为更改的点）

运用动态开点，保存每个节点的左右儿子编号，在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化了。

简化一下问题：求区间 $[1, r]$ 的区间第 $k$ 小值。直接找到 $r$ 时的根节点版本，再用权值线段树查找即可。

我们可以发现，主席树统计的信息也满足前缀和的性质，所以只需要用 $[1, r]$ 的信息减去 $[1, l - 1]$ 的信息就得到了区间 $[l, r]$ 的信息。

复杂度

时间复杂度

建树和离散化的时间复杂度都为 $O (n \log n)$ ，单次插入（只用修改 $\log n$ 个节点）和单次查询时的时间复杂度都是 $O (\log n)$ 的，所以总时间复杂度 $O (n \log n)$ ，并不难理解。

空间复杂度

考虑所有建立的结点的个数，建树有 $2 n - 1$ 个节点，每次插入/修改添加 $\log n$ 个节点，至多添加 $n \log n$ 个点，总共需要的空间为 $2 n - 1 + n \log n$ ，当 $n \leq 10^{5}$ 时，约等于 $20 \times 10^{5}$ ；

提示：千万不要吝啬空间（大多数题目中空间限制都较为宽松，因此一般不用担心空间超限的问题）！大胆一点，直接上个 $2^{5} \times 10^{5}$ ，接近原空间的两倍。

Code

cpp

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a[N],unq[N];
struct Tree {
	int val;
	int ls,rs; 
} tree[N<<5];
int id[N],iCnt;
inline void build(int &rt,int l,int r) {
	rt=++iCnt;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(tree[rt].ls,l,mid);
	build(tree[rt].rs,mid+1,r);
	return ;
}
inline void update(int &rt,int pre,int l,int r,int p) {
	rt=++iCnt;
	tree[rt]=tree[pre];
	tree[rt].val++;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	if(p<=mid) update(tree[rt].ls,tree[pre].ls,l,mid,p);
	if(p>mid) update(tree[rt].rs,tree[pre].rs,mid+1,r,p);
	return ;
}
inline int query(int nl,int nr,int l,int r,int k) {
	if(l==r)
		return unq[l];
	int x=tree[tree[nr].ls].val-tree[tree[nl].ls].val;
	int mid=(l+r)>>1;
	if(x>=k) return query(tree[nl].ls,tree[nr].ls,l,mid,k);
	if(x<k) return query(tree[nl].rs,tree[nr].rs,mid+1,r,k-x); 
}
signed main() {
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		unq[i]=a[i];
	}
	sort(unq+1,unq+n+1);
	int num=unique(unq+1,unq+n+1)-unq-1;
	build(id[0],1,num);
	for(int i=1;i<=n;i++) {
		int p=lower_bound(unq+1,unq+num+1,a[i])-unq;
		update(id[i],id[i-1],1,num,p);
	}
	for(int i=1;i<=m;i++) {
		int l,r,k;
		scanf("%lld%lld%lld",&l,&r,&k);
		printf("%lld\n",query(id[l-1],id[r],1,num,k)); 
	}
	return 0;
}

[国家集训队] middle

前言

如果支持离线算法，或者带修，还能离线后整体二分做？？？

简要题意

给出一个长度为 $n$ 的序列 $a$ ， $q$ 次询问 $(a, b, c, d)$ 求区间 $[l, r]$ 最大的中位数，其中 $l \in [a, b], r \in [c, d]$ ，强制在线。

Solution

先想到一个小trick：求中位数可以优先考虑二分答案，二分到 $x$ 时将区间内中所有 $\geq x$ 的数赋为 $1$ ，反之赋为 $- 1$ ，并对其做求和得到 $s u m$ ；

若 $s u m \geq 0$ 说明最优的答案 $a n s \geq x$ ，否则反之。

中间区间 $[b + 1, c - 1]$ 的和（注意判断 $b + 1 \leq c - 1$ ）是不变的，那就要使得左区间 $[l, b]$ 和右区间 $[c, r]$ 的值最大，就转化成求左右区间最大前后缀和，这很明显是用线段树来维护，跟维护区间最大子段和的方法一样；

由于二分到不同的 $x$ 时对应的线段树版本不一样，考虑将线段树可持久化掉，在线处理。

怎么优化呢？对于两个线段树版本 $x, y (x < y)$ ，我们能观察到两个版本的区别在于，序列中 $x < a_{i} \leq y$ 的数在线段树上的权值从 $1$ 变为了 $- 1$ ，顺着思路，可以在询问前对序列 $a$ 从小到大排序，初始时树上的所有叶子节点的权值都为 $1$ ，按顺序加入 $a_{i}$ ，当前版本继承上一个版本，将 $a_{i}$ 在该版本的线段树上所对应的叶子节点的权值赋为 $- 1$ 并更新路径上经过的节点的左右儿子。

最后在二分答案的时候直接查询 $x$ 版本的线段树即可，时间复杂度为 $O (n \log^{2} n)$ 。

Code

cpp

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10;
int n,Q,q[5];
struct Node {
	int v,pos;	
} a[N];
struct Tree {
	int sum;
	int lmax,rmax;
	int ls,rs;
} tr[N*20];
int id[N],icnt;
inline void push_up(int rt) {
	tr[rt].sum=tr[tr[rt].ls].sum+tr[tr[rt].rs].sum;
	tr[rt].lmax=max(tr[tr[rt].ls].lmax,tr[tr[rt].ls].sum+tr[tr[rt].rs].lmax);
	tr[rt].rmax=max(tr[tr[rt].rs].rmax,tr[tr[rt].rs].sum+tr[tr[rt].ls].rmax);
	return ;
}
inline void build(int &rt,int l,int r) {
	rt=++icnt;
	if(l==r) {
		tr[rt].sum=tr[rt].lmax=tr[rt].rmax=1;
		return ;
	}
	int mid=(l+r)>>1;
	build(tr[rt].ls,l,mid);
	build(tr[rt].rs,mid+1,r);
	push_up(rt);
	return ;
}
inline void insert(int &rt,int pre,int l,int r,int x,int k) {
	rt=++icnt;
	tr[rt]=tr[pre];
	if(l==r) {
		tr[rt].sum=tr[rt].lmax=tr[rt].rmax=k;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) insert(tr[rt].ls,tr[pre].ls,l,mid,x,k);
	else insert(tr[rt].rs,tr[pre].rs,mid+1,r,x,k);
	push_up(rt);
	return ;
}
inline Tree Merge(Tree x,Tree y) {
	Tree z;
	z.sum=x.sum+y.sum;
	z.lmax=max(x.lmax,x.sum+y.lmax);
	z.rmax=max(y.rmax,y.sum+x.rmax);
	return z;
} 
inline Tree query(int rt,int l,int r,int s,int t) {
	if(s<=l&&r<=t)
		return tr[rt];
	int mid=(l+r)>>1;
	if(s<=mid&&mid<t)
		return Merge(query(tr[rt].ls,l,mid,s,t),query(tr[rt].rs,mid+1,r,s,t));
	if(s<=mid)
		return query(tr[rt].ls,l,mid,s,t);
	return query(tr[rt].rs,mid+1,r,s,t);
}
inline bool check(int x,int l1,int r1,int l2,int r2) {
	int Sum=0;
	if(r1+1<=l2-1)
		Sum+=query(id[x-1],1,n,r1+1,l2-1).sum;
	Sum+=query(id[x-1],1,n,l1,r1).rmax;
	Sum+=query(id[x-1],1,n,l2,r2).lmax;
	if(Sum>=0)
		return true;
	return false;
}
inline bool cmp(Node x,Node y) {
	return x.v<y.v;
}
signed main() {
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) {
		scanf("%lld",&a[i].v);
		a[i].pos=i;
	}
	sort(a+1,a+n+1,cmp);
	build(id[0],1,n);
	for(int i=1;i<=n;i++)
		insert(id[i],id[i-1],1,n,a[i].pos,-1);
	scanf("%lld",&Q); 
	int lastans=0;
	while(Q--) {
		for(int i=1;i<=4;i++) {
			scanf("%lld",&q[i]);
			q[i]=(q[i]+lastans)%n+1;
		}
		sort(q+1,q+4+1);
		int l=0,r=n+1;
		while(l+1<r) {
			int mid=(l+r)>>1;
			if(check(mid,q[1],q[2],q[3],q[4]))
				l=mid;
			else r=mid;
		}
		printf("%lld\n",a[l].v);
		lastans=a[l].v;
	}
	return 0;
}

[COCI 2020/2021 #3] Specijacija

简要题意

给定一棵 $n$ 层的树，第 $i$ 有 $i$ 个节点，其中每一层都是由上一层节点按以下方式得到：

其中一个节点有两个儿子；
其余节点都只有一个儿子；
所有节点按从上到下，从左到右的顺序编号。

给出每一层有两个儿子的节点编号 $a_{i}$ 就可以唯一确定下来这棵树。

$q$ 次询问，每次给定两个节点编号 $x, y$ ，求 $l c a (x, y)$ 的编号，强制在线。

Solution

我们钦定儿子个数不为 $1$ 的点为稀点，一棵树上总共有 $2 n + 1$ 个稀点，其中有 $n$ 个点有两个儿子， $n + 1$ 个是叶子结点（没有儿子）。

考虑建立一棵新的数将稀点连接起来，称这课树为稀树。

将原树上相邻两个稀点之间的所有的点构成一条链，链上的点必然是编号小作为编号大的祖先。

定义 $p_{i}$ 表示 $i$ 所在链的编号，对于两个节点 $x, y$ ：

若 $x$ 和 $y$ 在同一条链上，则答案必然为编号更小的点；
令 $p_{z} = l c a (p_{x}, p_{y})$ ：
- 若 $p_{x} = p_{z}$ ，则答案为 $x$ ；
- 若 $p_{y} = p_{z}$ ，同理；
- 若以上皆不满足，则答案为链 $p_{z}$ 的底部的点的编号。

令 $a_{i} = a_{i} - \frac{i (i - 1)}{2}$ ，表示其在原树的第 $i$ 层中从左往右数的编号。

题目转化成了如何快速求每个点所在的链的编号，发现相邻两层之间节点的个数差为 $1$ ，本质就在于当前层上稀点的位置从 $2$ 个点变成了 $1$ 个点，其余位置所在的链编号不变；

不妨从下往上维护每一层的信息，每往上一层，需要支持 单点删除，单点修改，查询第 $k$ 个数的链编号 的操作，可以使用线段树来维护。

在最底层建树，把线段树可持久化掉，每一层在上一层的版本上基础上更新新版本，具体的：

线段树上的点维护区间内链的个数，并在叶子节点上维护所在链的编号，对于当前层上的稀点 $x$ ，其两个儿子分别 $y_{1}, y_{2}$ ，在上一个版本的基础上删掉 $y_{2}$ 的信息并修改 $y_{1}$ 位置上的链的编号，最后查询 $(x, y)$ 时找到 $x$ 和 $y$ 在原树上的层数，并调用该层的版本查询即可。

这里把 $n, q$ 看作同阶，时间复杂度为 $O (n \log n)$ ；

空间复杂度：

建树 $n \log n$ ，一次单点删除和修改各 $\log n$ ，总体为 $3 n \log n$ 的复杂度。

Code

cpp

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int M=520520;
int n,q,t,a[N];
struct Tree {
	int id,c;
	int ls,rs;
} tr[N*3*20];
struct Node {
	int to,nxt;
	Node() {
		to=nxt=0;
	}
	Node(int a,int b) {
		to=a,nxt=b;
	}
} adj[M<<1];
int head[M],idx;
int id[N],icnt;
int num[N],tot,p[M];
int dep[M],f[M][22];
inline int calc(int x) {
	return x*(x+1)/2;
}
inline void add(int x,int y) {
	adj[++idx]=Node(y,head[x]);
	head[x]=idx;
	return ;
}
inline void dfs(int u,int fa) {
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<=20;i++)
		f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=adj[i].nxt) {
		int v=adj[i].to;
		if(v==fa)
			continue;
		dfs(v,u); 
	}
	return ;
}
inline int lca(int x,int y) {
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=20;i>=0;i--) {
		if(dep[f[x][i]]>=dep[y])
			x=f[x][i];
	}
	if(x==y)
		return x;
	for(int i=20;i>=0;i--) {
		if(f[x][i]!=f[y][i]) {
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
inline void push_up(int rt) {
	tr[rt].c=tr[tr[rt].ls].c+tr[tr[rt].rs].c;
	return ;
}
inline void build(int &rt,int l,int r) {
	rt=++icnt;
	if(l==r) {
		tr[rt].id=++tot;
		tr[rt].c=1;
		return ;
	}
	int mid=(l+r)>>1;
	build(tr[rt].ls,l,mid);
	build(tr[rt].rs,mid+1,r);
	push_up(rt);
	return ;
}
inline void clone(int &rt,int pre) {
	rt=++icnt;
	tr[rt]=tr[pre];
	return ;
}
inline void update(int &rt,int pre,int l,int r,int x,int k,int c) {
	clone(rt,pre);
	if(l==r) {
		tr[rt].id=k;
		tr[rt].c=c;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=tr[tr[rt].ls].c) update(tr[rt].ls,tr[pre].ls,l,mid,x,k,c);
	else update(tr[rt].rs,tr[pre].rs,mid+1,r,x-tr[tr[rt].ls].c,k,c);
	push_up(rt);
	return ;
}
inline int query(int rt,int l,int r,int x) {
	if(l==r)
		return tr[rt].id;
	int mid=(l+r)>>1;
	if(x<=tr[tr[rt].ls].c) return query(tr[rt].ls,l,mid,x);
	return query(tr[rt].rs,mid+1,r,x-tr[tr[rt].ls].c);
}
signed main() {
	scanf("%lld%lld%lld",&n,&q,&t);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	int m=calc(n+1);
	for(int i=1;i<=n+1;i++)
		num[i]=calc(i);
	for(int i=1;i<=n+1;i++)
		p[i]=calc(n)+i;
	build(id[n+1],1,n+1);
	for(int i=n;i>=1;i--) {
		int pos=a[i]-calc(i-1);
		p[++tot]=a[i];
		int x=query(id[i+1],1,n+1,pos);
		int y=query(id[i+1],1,n+1,pos+1);
		add(tot,x),add(x,tot);
		add(tot,y),add(y,tot);
		clone(id[i],id[i+1]);
		update(id[i],id[i],1,n+1,pos+1,0,0);
		update(id[i],id[i],1,n+1,pos,tot,1);
	}
	dfs(tot,0);
	int lastans=0;
	while(q--) {
		int x,y;
		scanf("%lld%lld",&x,&y);
		x=(x-1+t*lastans)%m+1;
		y=(y-1+t*lastans)%m+1;
		int dx=lower_bound(num+1,num+n+1+1,x)-num;
		int dy=lower_bound(num+1,num+n+1+1,y)-num;
		int px=query(id[dx],1,n+1,x-calc(dx-1));
		int py=query(id[dy],1,n+1,y-calc(dy-1));
		if(px==py) {
			lastans=min(x,y);
			printf("%lld\n",lastans);
			continue;
		}
		int pz=lca(px,py);
		if(px==pz)
			lastans=x;
		else {
			if(py==pz)
				lastans=y;
			else lastans=p[pz];
		}
		printf("%lld\n",lastans);
	}
	return 0;
}

Count on a tree

闲话

做完这题，对可持久化线段树的最主要用法：查询静态区间第 $k$ 小，又有了更进一步的思考和理解，其实应该在做完模版题后就来做这题，做了其他题后反而把思维局限了。

一开始想了一种类似于上面的【middle】的二分+树链剖分+可持久化线段树的 $O (n \log^{3} n)$ 做法...

简要题意

给定一棵 $n$ 个节点的树， $m$ 个询问 $u, v, k$ ，求 $u$ 和 $v$ 两点间第 $k$ 小的点权，强制在线。

Solution

结构其实和模版题差不多，只不过把序列问题转化为了树上问题。

对于点对 $(x, y)$ 的树上差分为 $s_{x} + s_{y} - s_{z} - s_{f a_{z}}$ ，其中 $z = l c a (x, y)$ ；

从根开始遍历整棵树，对于当前节点 $u$ 的儿子 $v$ ，继承 $u$ 的线段树版本，并在新版本上插入 $a_{v}$ 即可，复杂度为 $O (n \log n)$ 。

反思

一开始想的是树链剖分的建树，并按 dfn 序的顺序继承版本，很错误还很复杂。so，有时候不要被树链剖分给带偏了方向！！！

Code

cpp

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,a[N];
struct Node {
	int to,nxt;
	Node() {
		to=nxt=0;
	}
	Node(int a,int b) {
		to=a,nxt=b;
	}
} adj[N<<1];
struct Tree {
	int sum;
	int ls,rs;
} tr[N<<5];
int head[N],idx;
int num,unq[N];
int id[N],icnt;
int dep[N],f[N][22];
inline void add(int x,int y) {
	adj[++idx]=Node(y,head[x]);
	head[x]=idx;
	return ;
}
inline void push_up(int rt) {
	tr[rt].sum=tr[tr[rt].ls].sum+tr[tr[rt].rs].sum;
	return ;
}
inline void build(int &rt,int l,int r) {
	rt=++icnt;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	build(tr[rt].ls,l,mid);
	build(tr[rt].rs,mid+1,r);
	push_up(rt);
	return ;
}
inline void update(int &rt,int pre,int l,int r,int x) {
	rt=++icnt;
	tr[rt]=tr[pre];
	if(l==r) {
		tr[rt].sum=1;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(tr[rt].ls,tr[pre].ls,l,mid,x);
	if(mid<x) update(tr[rt].rs,tr[pre].rs,mid+1,r,x);
	push_up(rt);
	return ;
}
inline int query(int nx,int ny,int nz,int nf,int l,int r,int k) {
	if(l==r)
		return unq[l];
	int mid=(l+r)>>1;
	int sl=tr[tr[nx].ls].sum+tr[tr[ny].ls].sum-tr[tr[nz].ls].sum-tr[tr[nf].ls].sum;
	if(k<=sl) return query(tr[nx].ls,tr[ny].ls,tr[nz].ls,tr[nf].ls,l,mid,k);
	return query(tr[nx].rs,tr[ny].rs,tr[nz].rs,tr[nf].rs,mid+1,r,k-sl);
}
inline void dfs(int u,int fa) {
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<=20;i++)
		f[u][i]=f[f[u][i-1]][i-1];
	int p=lower_bound(unq+1,unq+num+1,a[u])-unq;
	update(id[u],id[fa],1,num,p);
	for(int i=head[u];i;i=adj[i].nxt) {
		int v=adj[i].to;
		if(v==fa)
			continue;
		dfs(v,u);
	}
	return ;
}
inline int lca(int x,int y) {
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=20;i>=0;i--) {
		if(dep[f[x][i]]>=dep[y])
			x=f[x][i];
	} 
	if(x==y)
		return x;
	for(int i=20;i>=0;i--) {
		if(f[x][i]!=f[y][i]) {
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
signed main() {
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		unq[i]=a[i];
	}
	for(int i=1;i<n;i++) {
		int x,y;
		scanf("%lld%lld",&x,&y);
		add(x,y),add(y,x);
	}
	sort(unq+1,unq+n+1);
	num=unique(unq+1,unq+n+1)-unq-1;
	build(id[0],1,num);
	dfs(1,0);
	int lastans=0;
	while(m--) {
		int x,y,k;
		scanf("%lld%lld%lld",&x,&y,&k);
		x^=lastans;
		int z=lca(x,y);
		lastans=query(id[x],id[y],id[z],id[f[z][0]],1,num,k);
		printf("%lld\n",lastans);
	}
	return 0;
}

总结

可持久化线段树是一种类似前缀和的数据结构，具有和前缀和类似的区间加减及差分等性质，常通过记录历史版本实现查询静态区间第 $k$ 小值等操作。

也可以将离线时线段树的维护操作可持久化掉，强转在线；

多去观察题目中不同历史版本之间的关系，若新版本可以由上一个版本通过单点/区间的修改/删除操作更新，可考虑使用可持久化线段树优化。

可持久化栈

引入

可持久优化栈时一种支持 栈顶修改，栈顶查询，回退历史版本 的一种数据结构。

由于手写栈依赖于数组，也可以用可持久优化 数组（或线段树） 来模拟栈，单次插入/删除时间复杂度 $O (\log n)$ ，空间复杂度 $O (n \log n)$ ，其优势是可以随机访问栈中元素，但很多情况并没有这种需求；

省去随机访问的需求后，可持久化栈可以做到单次修改时间复杂度 $O (1)$ ，空间复杂度 $O (n)$ ，在线性的时间内就可以解决问题。

[USACO10OPEN] Time Travel S

Solution

$s t k_{i}$ 表示栈中从底向上添加的第 $i$ 个元素的值（其中 $s t k_{t o p}$ 为栈顶元素）；

$t o p$ 表示当前的栈顶编号；

$i d_{i}$ 表示第 $i$ 次操作的栈顶编号；

$p r e_{i}$ 表示第 $i$ 个元素的前驱。

插入

向栈顶加入新元素，并记录这次操作的栈顶编号和前驱编号。

cpp

stk[++top]=x;
id[i]=top;
pre[id[i]]=id[i-1];

删除

只需要把上一次加入的元素（前驱）复制到当前即可。

cpp

id[i]=pre[id[i-1]];

版本跳跃

注意题目要求，此题时回到第 $x$ 此操作前，也就是第 $x - 1$ 次操作，直接复制过来即可。

cpp

id[i]=id[x-1];

查询

第 $i$ 次操作时的栈顶为 $i d_{i}$ ，栈顶元素为 $s t k_{i d_{i}}$ 。

Code

cpp

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,id[N],pre[N];
int stk[N],top;
signed main() {
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) {
		char op;
		scanf(" %c",&op);
		if(op=='a') {
			int x;
			scanf("%lld",&x);
			stk[++top]=x;
			id[i]=top;
			pre[id[i]]=id[i-1];
		}
		if(op=='s')
			id[i]=pre[id[i-1]];
		if(op=='t') {
			int x;
			scanf("%lld",&x);
			id[i]=id[x-1];
		}
		if(!id[i]) printf("-1\n");
		else printf("%lld\n",stk[id[i]]);
	}
	return 0;
}

后记

可能有些的不足的地方，多多包涵！！！

特别鸣谢 & 部分内容的参考文献

OI Wiki

前言 ​

可持久化 ​

关于主席树和可持久化线段树的区别 ​

关于 log⁡n 和 log2⁡n 的区别 ​

可持久化线段树 ​

引入 ​

解析 ​

复杂度 ​

时间复杂度 ​

空间复杂度 ​

[国家集训队] middle ​

前言 ​

简要题意 ​

Solution ​

[COCI 2020/2021 #3] Specijacija ​

简要题意 ​

Solution ​

Count on a tree ​

闲话 ​

简要题意 ​

Solution ​

反思 ​

总结 ​

可持久化栈 ​

引入 ​

[USACO10OPEN] Time Travel S ​

Solution ​

插入 ​

删除 ​

版本跳跃 ​

查询 ​

后记 ​

特别鸣谢 & 部分内容的参考文献 ​

前言

可持久化

关于主席树和可持久化线段树的区别

关于 $\log n$ 和 $\log_{2} n$ 的区别

可持久化线段树

引入

解析

复杂度

时间复杂度

空间复杂度

[国家集训队] middle

前言

简要题意

Solution

[COCI 2020/2021 #3] Specijacija

简要题意

Solution

Count on a tree

闲话

简要题意

Solution

反思

总结

可持久化栈

引入

[USACO10OPEN] Time Travel S

Solution

插入

删除

版本跳跃

查询

后记

特别鸣谢 & 部分内容的参考文献