题目描述
你将要实现一个功能强大的整数序列编辑器。
在开始时,序列是空的。
编辑器共有五种指令,如下:
1、“I x”,在光标处插入数值x。
2、“D”,将光标前面的第一个元素删除,如果前面没有元素,则忽略此操作。
3、“L”,将光标向左移动,跳过一个元素,如果左边没有元素,则忽略此操作。
4、“R”,将光标向右移动,跳过一个元素,如果右边没有元素,则忽略次操作。
5、“Q k”,假设此刻光标之前的序列为
a1,a2,…,an
输出max1≤i≤kSi,其中Si=a1+a2+…+ai。输入格式第一行包含一个整数Q表示指令的总数。
接下来Q行,每行一个指令,具体指令格式如题目描述。
输出格式
每一个“Q k”指令,输出一个整数作为结果,每个结果占一行。
数据范围
1≤Q≤10^6,
|x|≤10^3,
1≤k≤n
样例
8
I 2
I -1
I 1
Q 3
L
D
R
Q 2
2
3
C++ 代码
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
stack<int> Left,Right;//一个存光标左边的一个存光标右边的
int sum[1000100],sum_max[1000100];//一个用来保存当前的前缀和,一个用来保存当前最大的前缀和
int main()
{
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin>>T;
memset(sum_max,0x8f,sizeof sum_max);//初始化为负无穷,输入的数有负数,最大前缀和可能为负,这里一开始没想到
int sumtop=0;//你懂的
while(T--)
{
char c[2];
int num;
//接下来就是分类讨论了
cin>>c;
if(*c=='I')
{
cin>>num;
Left.push(num);
sum[++sumtop]=num+sum[sumtop-1];//求前缀和
sum_max[sumtop]=max(sum[sumtop],sum_max[sumtop-1]);//求此时的最大的前缀和
}
if(*c=='D'&&!Left.empty())//当Left非空
{
Left.pop();sumtop--;
}
if(*c=='L'&&!Left.empty())//当Left非空
{
Right.push(Left.top()),Left.pop();//右边存入,左边取出
sumtop--;
}
if(*c=='R'&&!Right.empty())//当Right非空
{
Left.push(Right.top()),Right.pop();//左边存入,右边取出
sumtop++;
sum[sumtop]=Left.top()+sum[sumtop-1];//更新前缀和
sum_max[sumtop]=max(sum[sumtop],sum_max[sumtop-1]);//更新最大前缀和
}
if(*c=='Q')cin>>num,cout<<sum_max[num]<<'\n';//输出
}
return 0;
}