编辑器

AcWing-128-编辑器

分析

见《进阶指南》第50页。

对顶栈。

实现

#include <iostream>
#include <stack>
using namespace std;

const int N = 1000010;
stack<int> l, r;
int l_sum, max_sum[N];

void push (int val) {
    l.push(val);
    l_sum += val;
    if (l.size() == 1)
        max_sum[l.size()] = l_sum;
    else
        max_sum[l.size()] = max(max_sum[l.size() - 1], l_sum);
}

int main () {
    int T;
    scanf("%d", &T);
    while (T --) {
        char opt[5];
        scanf("%s", opt);
        if (opt[0] == 'I') {
            int x;
            scanf("%d", &x);
            push(x);
        } else if (opt[0] == 'D') {
            if (!l.empty()) {
                l_sum -= l.top();
                l.pop();
            }
        } else if (opt[0] == 'L') {
            if (!l.empty()) {
                l_sum -= l.top();
                r.push(l.top());
                l.pop();
            }
        } else if (opt[0] == 'R') {
            if (!r.empty()) {
                push(r.top());
                r.pop();
            }
        } else { // Q k
            int k;
            scanf("%d", &k);
            printf("%d\n", max_sum[k]);
        }
    }
    return 0;
}