题目链接：128. 编辑器 - AcWing题库

标签：堆顶栈

思路：分别用两个栈，记录光标左边的数和光标右边的数；用s记录前缀和，f记录最大前缀。

对题目所示五个操作有：

1.插入操作：将x插入到L栈中。

2.删除操作：删除L栈的顶部元素。

3.光标左移：将L栈的顶部元素push到R栈

4.光标右移：将R栈的顶部元素push到L栈

5.查询操作：输出f[k]

对于前k个数的最大前缀，可能等于前k-1个数的最大前缀 或者 前k个数的和

即：f[k]=max(f[k-1],s[k])

注意：注意空栈！

代码：

#include<iostream>
#include<stack>
#include<cstring>
using namespace std;const int N = 1000010;int n,x;
char op;
int s[N],f[N];
int l[N],r[N],len1,len2;int main()
{memset(f,-0X3f,sizeof f);cin>>n;for(int i=1;i<=n;i++) {cin>>op;if(op=='I'){cin>>x;l[++len1]=x;s[len1]=s[len1-1]+x;f[len1]=max(f[len1-1],s[len1]);}else if(op=='D'){if(len1>0) len1--;}else if(op=='L'){if(len1>0){x = l[len1];len1--;r[++len2]=x;}}else if(op=='R'){if(len2>0){x = r[len2];len2--;l[++len1]=x;s[len1]=s[len1-1]+x;f[len1]=max(f[len1-1],s[len1]);}}else if(op=='Q'){cin>>x;cout<<f[x]<<endl;}}return 0;
}