编辑器

题目要求：你将要实现一个功能强大的整数序列编辑器。在开始时，序列是空的。编辑器共有五种指令，如下：
- 1、“I x”，在光标处插入数值x。
- 2、“D”，将光标前面的第一个元素删除，如果前面没有元素，则忽略此操作。
- 3、“L”，将光标向左移动，跳过一个元素，如果左边没有元素，则忽略此操作。
- 4、“R”，将光标向右移动，跳过一个元素，如果右边没有元素，则忽略次操作。
- 5、“Q k”，假设此刻光标之前的序列为a1,a2,…,an,输出max1≤i≤kSi，其中Si=a1+a2+…+ai。

输入格式：
第一行包含一个整数Q，表示指令的总数。
接下来Q行，每行一个指令，具体指令格式如题目描述。

输出格式：
每一个“Q k”指令，输出一个整数作为结果，每个结果占一行。

数据范围：
$1≤Q≤10^6$
$|x|≤10^3,$
$1≤k≤n$

输入样例：

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

输出样例：

2
3

思路：用两个栈来维护：左边的栈sl和右边的栈sr。
- 当插入一个元素的时候相当于左边的栈sl插入一个元素，同时需要更新前缀和数组s及前缀和数组的前i个数的最小值数组f
- 当删除一个元素时相当于删除左边的栈sl的栈顶元素
- 当向左移动时相当于左边的栈sl的栈顶元素出栈，并将该元素放入右边的栈sr入栈
- 当向右移动时时同理
- 查询时输出前缀和数组的前i个数的最小值数组f对应位置的值即可

程序(CPP)：

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

const int maxn = 1e6+10;
int sl[maxn], sr[maxn], tl, tr;  // 左右两个栈及其栈顶位置
int s[maxn], f[maxn]; // 前缀和数组和保留前i个数的最小值
void push_l(int x)
{
    sl[++tl] = x;
    s[tl] = s[tl-1]+x;
    f[tl] = max(f[tl-1], s[tl]);
}

int main()
{
    int Q; cin >> Q;
    f[0] = INT_MIN;
    while(Q--)
    {
        char t; cin >> t;
        int x;
        if(t=='I')
        {
            cin >> x;
            push_l(x);
        }
        else if(t=='D')
        {
            if(tl>0) tl--;
        }
        else if(t=='L')
        {
            if(tl>0) sr[++tr] = sl[tl--];
        }
        else if(t=='R')
        {
            if(tr>0) push_l(sr[tr--]);
        }
        else if(t=='Q')
        {
            cin >> x;
            cout << f[x] << endl;
        }
    }
    return 0;
}