可持久化栈学习笔记 | 题解 P6182 [USACO10OPEN]Time Travel S

简要题意

你需要维护一个栈，有 \(n\) 个操作，支持：

给定一个 \(x\)，将 \(x\) 加入栈。
将一个元素出栈。
给定一个 \(x\)，将当前栈回退到 第 \(x\) 操作前。

每一次操作结束后，你需要输出栈顶元素。如果当前栈是一个空栈，那么输出 \(-1\)。

数据保证操作合法，且 \(1 \le n \le 8 \times 10^{4}\)。

思路

据说本题存在 \(O(n)\) 做法，但是我不会，这里有一个 \(O(n\log n)\) 做法。

对于回退之类的字眼，我们肯定会想到可持久化，由于栈一般时用数组实现的，所以我们可以写一个可持久化数组。如果不会可持久化数组，请去做模板题。

下面有一个用数组实现的栈的简要代码，对于分析很有帮助：

int stk[114514],t;

void push(int v){

	stk[++t]=v;

}

void pop(){

	t--;

}

int top(){

	return (t==0)?(-1):(stk[t]);

}

我们可以考虑用可持久化数组来维护 stk，那么 \(t\) 怎么办？我们发现，\(t\) 需要是一个可持久化变量，可持久化变量不就是数组吗？于是我们直接使用数组 \(T_i\) 来表示第 \(i\) 次操作后栈顶指针 \(t\)。

整个代码时间复杂度和空间复杂度都是 \(O(n\log n)\) 的（可持久化的开销）。

代码

#include <bits/stdc++.h>

#define mid ((l+r)>>1)

using namespace std;

const int SIZE = 8e4+5;

struct{

	int l,r,v;

}t[SIZE*25];

int top;

int root[SIZE*25];

int n;

int newnode(int i){

	t[++top]=t[i];

	return top;

}

int update(int i,int l,int r,int p,int val){

	i=newnode(i);

	if(l==r){

		t[i].v=val;

		return i;

	}

	if(p<=mid){

		t[i].l=update(t[i].l,l,mid,p,val);

	}

	else{

		t[i].r=update(t[i].r,mid+1,r,p,val);

	}

	return i;

}

int query(int i,int l,int r,int p){

	if(l==r){

		return t[i].v;

	}

	if(p<=mid){

		return query(t[i].l,l,mid,p);

	}

	else{

		return query(t[i].r,mid+1,r,p);

	}

}

int stop[SIZE];

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	cin>>n;

	for(int i=1;i<=n;i++){

		root[i]=root[i-1];

		stop[i]=stop[i-1];

		char op;

		int x;

		cin>>op;

		if(op=='a'){

			cin>>x;

			root[i]=update(root[i-1],1,n,(++stop[i]),x);

		}

		else if(op=='s'){

			stop[i]--;

		}

		else{

			cin>>x;

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

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

		}

		if(stop[i]!=0){

			cout<<query(root[i],1,n,stop[i])<<'\n';

		}

		else{

			cout<<-1<<'\n';

		}

	}

	return 0;

}

跑了 \(113\) 毫秒，比 \(O(n)\) 的慢。

AC Record

巴特西

可持久化栈学习笔记 | 题解 P6182 [USACO10OPEN]Time Travel S

简要题意

思路

代码

最新文章

热门文章