🎈 原创

洛谷 P2201 数列编辑器

题目描述

小Z是一个爱好数学的小学生。最近，他在研究一些关于整数数列的性质。

为了方便他的研究，小Z希望实现一个叫做“Open Continuous Lines Processor”的数列编辑器。

一开始，数列编辑器里没有数字，只有一个光标。这个数列编辑器需要支持五种操作。

• I x 在当前光标前插入数字 x。

• D 删除当前光标前的数字。

• L 光标向前移动一个数字。

• R 光标向后移动一个数字。

• Q k 设光标之前的数列是{a1，a2，……，an}，输出第k位及之前最大的前缀和，保证k≤n。

输入格式

第一行包含一个数字 N ，表示操作的个数。

接下来包含 N 行，每行包含一条命令。

输出格式

对于每个Q k 命令，输出一个整数表示这个操作的答案。

输入输出样例

输入 #1复制

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

输出 #1复制

2
3

说明/提示

【数据规模】

对于 50% 的数据，N ≤ 1000；

对于 80% 的数据，N ≤ 100000；

对于 100% 的数据，N ≤ 1000000，插入的数字绝对值大小不会超过 1000。

---

用两个栈来表示光标的左侧和右侧，L时Left栈出栈，Right栈进栈，反之亦然。同时维护一个前缀和数组和一个前缀和最大值的数组。只有当Left栈进栈新的元素后才需要更新这两个数组

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

stack<int> Left, Right;
int pre[1000010] = {0}, N, preMax[1000010] = {0};

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    preMax[0] = -0x7fffffff;
    for(int i = 0; i < N; i++)
    {
        char op;
        cin >> op;
        if(op == 'I')
        {
            int temp;
            cin >> temp;
            Left.push(temp);
            pre[Left.size()] = pre[Left.size() - 1] + Left.top();
            preMax[Left.size()] = max(preMax[Left.size() - 1], pre[Left.size()]);
        }
        else if(op == 'D')
            Left.pop();
        else if(op == 'L')
        {
            Right.push(Left.top());
            Left.pop();
        }
        else if(op == 'R')
        {
            Left.push(Right.top());
            Right.pop();
            pre[Left.size()] = pre[Left.size() - 1] + Left.top();
            preMax[Left.size()] = max(preMax[Left.size() - 1], pre[Left.size()]);
        }
        else if(op == 'Q')
        {
            int temp;
            cin >> temp;
            cout << preMax[temp] << endl;
        }
    }

    return 0;
}