主席树暴力维护

#include<bits/stdc++.h>
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
using namespace std;
typedef long long ll;
int q;
struct N{
	int ls,rs,c;
}tr[15000010];
int rt[500010],l[500010],r[500010],id;
void change(int pre,int &now,int l,int r,int x,int v){
	tr[now=++id]=tr[pre];
	if(l==r){
		tr[now].c=v;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)change(lc(pre),lc(now),l,mid,x,v);
	else change(rc(pre),rc(now),mid+1,r,x,v);
}
int find(int p,int l,int r,int x){
	if(l==r)return tr[p].c;
	int mid=(l+r)>>1;
	if(x<=mid)return find(lc(p),l,mid,x);
	else return find(rc(p),mid+1,r,x);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>q;
	l[0]=1;
	for(int i=1;i<=q;i++){
		int op,t,x;
		cin>>op>>t;t++;
		if(op==0){
			cin>>x;
			l[i]=l[t];r[i]=r[t]+1;
			change(rt[t],rt[i],1,q,r[i],x);
		}
		else{
			l[i]=l[t]+1;r[i]=r[t];rt[i]=rt[t];
			cout<<find(rt[i],1,q,l[t])<<'\n';
		}
	}
	return 0;
}

我们将添加操作视作添加一个新的点。则易发现最终会形成一棵树。

删除操作就是将一个版本的头部向下移一个点。所以用 st 表维护。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N],st[N][25],head[N],tail[N],len,l[N];
signed main()
{
	int q;cin>>q;
	for(int i=1;i<=q;i++)
	{
		int op,x,y;cin>>op;
		if(op==0)
		{
			cin>>x>>y;x++;
			tail[i]=++len;a[len]=y;l[i]=l[x]+1;
			head[i]=head[x];if(l[x]==0)head[i]=len;
			st[len][0]=tail[x];for(int i=1;i<=20;i++)st[len][i]=st[st[len][i-1]][i-1];
		}
		else
		{
			cin>>x;x++;
			tail[i]=tail[x];l[i]=l[x]-1;
			cout<<a[head[x]]<<'\n';
			int pos=tail[i],s=l[i]-1;
			for(int i=20;i>=0;i--)if(s>=(1<<i))s-=(1<<i),pos=st[pos][i];
			head[i]=pos;
		}
	}
	return 0;
}