HDU4699：Editor

浅谈栈：https://www.cnblogs.com/AKMer/p/10278222.html

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4699

用对顶栈模拟即可。\(stk1\)表示光标之前的数列，\(stk2\)表示光标之后的数列。然后维护一下前缀和以及前缀和的最大值即可。

对于插入，直接往\(stk1\)里扔这个数字然后更新\(sum\)和\(mx\)。

对于删除，直接弹栈\(stk1\)。

对于左移，弹栈\(stk1\)并把弹出来的元素压进\(stk2\)。

对于右移，弹栈\(stk2\)并把弹出来的元素压进\(stk1\)。

对于查询，输出\(mx_k\)即可。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e6+5;

char opt[5];

int n,top1,top2;

int stk1[maxn],stk2[maxn],mx[maxn],sum[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

void insert(int x) {

	stk1[++top1]=x;

	sum[top1]=sum[top1-1]+x;

	mx[top1]=max(mx[top1-1],sum[top1]);

}

int main() {

	mx[0]=-2e9;

	while(~scanf("%d",&n)) {

		top1=top2=0;

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

			scanf("%s",opt+1);

			if(opt[1]=='I') {

				int x=read();

				insert(x);

			}

			if(opt[1]=='D'&&top1)top1--;

			if(opt[1]=='L'&&top1)

				stk2[++top2]=stk1[top1],top1--;

			if(opt[1]=='R'&&top2)

				insert(stk2[top2]),top2--;

			if(opt[1]=='Q') {

				int k=read();

				printf("%d\n",mx[k]);

			}

		}

	}

	return 0;

}