题解
本题的特殊性在于，四种操作均在光标位置发生，并且发生完操作之后光标至多移动一个位置。根据这种始终在序列中间某个指定位置进行修改的性质，可以使用“对顶栈”算法。————《算法竞赛进阶指南》
有这种思想这道题就很好做了。实际上题目中的“最大前缀和”和求栈中最小值有点像，也算是使用栈的一个提示？1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using namespace std;
int Q, stf[1000005], tf, str[1000005], tr, st[1000005], t, sum = 0;
int main(){
while(scanf("%d", &Q) == 1){
tf = tr = t = 0, sum = 0, st[0] = -2000000000;
char ord[3];
int opr = 0;
while(Q--){
scanf("%s", ord);
if(ord[0] == 'I'){
scanf("%d", &opr);
stf[++tf] = opr, t++, sum += opr;
st[t] = max(st[t - 1], sum);
}
if(ord[0] == 'D') t--, sum -= stf[tf--];
if(ord[0] == 'L' && tf) sum -= stf[tf], str[++tr] = stf[tf--], t--;
if(ord[0] == 'R' && tr) {
stf[++tf] = str[tr--], t++, sum += stf[tf];
st[t] = max(st[t - 1], sum);
}
if(ord[0] == 'Q') scanf("%d", &opr), printf("%d\n", st[opr]);
}
}
return 0;
}