Editor

Editor

题目描述

$你将要实现一个功能强大的整数序列编辑器。

在开始时，序列是空的。

编辑器共有五种指令，如下：

1、I x，在光标处插入数值 x。
2、D，将光标前面的第一个元素删除，如果前面没有元素，则忽略此操作。
3、L，将光标向左移动，跳过一个元素，如果左边没有元素，则忽略此操作。
4、R，将光标向右移动，跳过一个元素，如果右边没有元素，则忽略次操作。
5、Q k，假设此刻光标之前的序列为 a1,a2,…,an，输出 max1≤i≤k Si，其中 Si=a1+a2+…+ai$

样例

输入样例：
8
I 2
I -1
I 1
Q 3
L
D
R
Q 2
输出样例：
2
3

算法

(对顶栈)

当对一个序列的中间元素进行操作时，用类似于对顶堆的思想，考虑用两个对顶栈来维护

定义左右双栈，左栈为光标左侧的元素，右栈为光标右侧的元素

对于第一个操作，我们直接往push 元素x

对于第二个操作，我们让pop

对于第三个操作我们将 的栈顶元素pop并且压入

对于第四个操作我们将 的栈顶元素pop并且压入

第五个操作，我们定义一个数组表示从的栈底到第i个元素的最大前缀和是多少

定义为从的栈底到第i个元素的前缀和是多少

初始化(前缀有可能是负数),每次执行完操作一时我们令：

当执行pop操作时top会-1相当于f[top]被删除

时间复杂度O(N)

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 1000010;
int stk0[N],stk1[N];
int tt[2];
int s[N],f[N];
int n;

int main()
{
    scanf("%d",&n);
    char op[2];
    int k;
    f[0] = -1e9 - 10;
    while(n --)
    {
        scanf("%s",op);
        if(*op == 'I')
        {
            scanf("%d",&k);
            stk0[++ tt[0]] = k;
            s[tt[0]] = s[tt[0] - 1] + k;
            f[tt[0]] = max(f[tt[0] - 1],s[tt[0]]);
        }else if(*op == 'D')
        {
            if(tt[0]) tt[0] --;
        }else if(*op == 'L')
        {
            if(tt[0]) stk1[++ tt[1]] = stk0[tt[0] --];
        }else if(*op == 'R')
        {
            if(tt[1]) 
            {
                stk0[++ tt[0]] = stk1[tt[1] --];
                s[tt[0]] = s[tt[0] - 1] + stk0[tt[0]];
                f[tt[0]] = max(f[tt[0] - 1],s[tt[0]]);
            }
        }else 
        {
            scanf("%d",&k);
            printf("%d\n",f[k]);
        }
    }
    return 0;
}