题目大意:
给定一个整数序列 维护5种操作 次数<1e6
I x: 光标位置插入x 然后光标位于x之后
D: 删除光标前一个数
L: 光标左移
R: 光标右移
Q k: 询问位置k之前的最大前缀和
选用"对顶栈"的做法 大致示意图如下:
对顶栈stkl, stkr直接通过数组模拟即可实现
以I x的操作为例, 需要:
1)将x插入stkl;
2)更新s数组 当前的前缀和 = 之前的前缀和 + x
3)更新f数组 记录该位置的最大前缀和
故有如下的代码:
// tl用于记录左栈的栈顶位置
void push_left(int x) {
stkl[++tl] = x;
s[tl] = s[tl-] + x;
f[tl] = max(f[tl-], s[tl]);
}
对于D操作 直接将左栈栈顶出栈 即--tl;
对于L 左栈弹出 压入右栈
对于R 弹出右栈 剩下操作同I x的2) 3)
对于Q k return f[k]即可
完整代码如下:
#include <bits/stdc++.h>
using namespace std; const int N = 1e8 + ; int stkl[N], stkr[N], tl, tr;
int s[N], f[N]; // s维护当前前缀和 f维护当前最大前缀和
char str[]; void push_left(int x) {
stkl[++tl] = x;
s[tl] = s[tl-] + x;
f[tl] = max(f[tl-], s[tl]);
} int main() {
int n;
while(~scanf("%d", &n)) {
f[] = INT_MIN;
tl = tr = ;
s[] = ;
while(n--) {
scanf("%s", str);
int x;
if(*str == 'I') {
scanf("%d", &x);
push_left(x);
}
if(*str == 'D') {
if(tl > ) tl--;
}
if(*str == 'L') {
if(tl > ) stkr[++tr] = stkl[tl--];
}
if(*str == 'R') {
if(tr > ) push_left(stkr[tr--]);
}
if(*str == 'Q') {
scanf("%d", &x);
printf("%d\n", f[x]);
}
}
}
}
这里注意一下每次的初始化即可
f[0] = INT_MIN;
tl = tr = 0;
s[0] = 0;