千万别把0当成最小的值…

懵逼的 题目

HDU

扯淡的 题解

看的LYD神仙的书Orz

我们发现这个光标把整个序列分成了两部分, 每一个部分都只会在一段进行操作

于是我们搞两个栈顶相对的栈, 然后模拟即可

不要忘记初始化maxfr[0] = -INF

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <stack>
#define MAXN (1000000 + 5)
#define INF (2000000000)
using namespace std;
int n, srx, fr[MAXN], maxfr[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    while (cin >> n)
    {
        string sre;
        stack<int> x, y;
        maxfr[0] = -INF;
        for (int i = 1; i <= n; i++)
        {
            cin >> sre;
            if (sre == "I" || sre == "Q")
                cin >> srx;
            if (sre == "I")
                x.push(srx), fr[x.size()] = fr[x.size() - 1] + srx, maxfr[x.size()] = max(maxfr[x.size() - 1], fr[x.size()]);
            else if (sre == "Q")
                cout << maxfr[srx] << endl;
            else if (sre == "L" && !x.empty())
                y.push(x.top()), x.pop();
            else if (sre == "R" && !y.empty())
                x.push(y.top()), fr[x.size()] = fr[x.size() - 1] + y.top(), maxfr[x.size()] = max(maxfr[x.size() - 1], fr[x.size()]), y.pop();
            else if (sre == "D" && !x.empty())
                x.pop();
        }
    }
    return 0;
}

By Cansult