#include<bits/stdc++.h>
using namespace std;
int q,x,y;
char c; // 操作
int s1[1000010],s2[1000010],top1,top2; // 两个栈
int sum[1000010],ans[1000010]={-1234567890}; // 前缀和以及最大值答案
int main(){
cin >>q;while(q--){
cin >> c;
if(c=='I'){ // 插入
cin >>x;
s1[++top1]=x;
sum[top1] = sum[top1-1]+s1[top1]; // 更新前缀和数组
ans[top1] = max(ans[top1-1],sum[top1]); // 更新答案
}if(c=='D'){ // 删除
top1--;
}if(c=='L'){ // 向前移动
s2[++top2] = s1[top1--];
}if(c=='R'){ // 向后移动
s1[++top1] = s2[top2--];
sum[top1] = sum[top1-1]+s1[top1]; // 同上
ans[top1] = max(ans[top1-1],sum[top1]);
}if(c=='Q'){ // 询问
cin >>x;
cout << ans[x] << endl;
}
}
return 0;
}
P2201 数列编辑器
题目简化
维护一个数列编辑器和一个光标。
每次进行操作：
I x在当前光标前插入数字 x。D删除当前光标前的数字。L光标向前移动一个数字。R光标向后移动一个数字。Q k设光标之前的数列是 {$a_1,a_2,⋯,a_n$}，输出第 k 位及之前最大的前缀和，保证 $k⩽n$。
题解
提示1
首先这道题的标签是模拟，这五种操作是不是很像一个链表？
提示2
注意Q操作，$n$相当于当前光标位置，$k\le n$，所以只需要处理光标之前的前缀和最大值。
解答
由于只有一个光标，链表的其他链相对多余，使用栈更方便，维护两个栈，一个记录光标以前的所有元素；另一个记录光标以后的所有元素，那么对于前四个操作，只需要在两个栈中来回操作即可。
对于第五个操作，由于它只需要输出前$n$个的前缀最大值，且当修改后面的数字时获取前面的答案不会改变，只需要维护当前光标前会改变的那位数字的前缀和以及前缀和最大值即可。
时间复杂度$O(q)$
注意
插入数据可能含有负数，前缀和最大值需要取到负数inf。