【题解】HDOJ P4699【Editor】

背景

又是一道万能老题,挂了好久了。

分析

这里可以用伸展树(然而我没学到),也可用对顶栈。
建立两个栈,栈$A$表示从序列开头到当前光标的位置这一段子序列,栈$B$表示从当前光标位置到序列结尾的这一段子序列,二者都以光标所在的那一端为栈顶。这两个栈合起来就表示了整个序列。因为查询操作的$k$不超过光标位置,所以用一个数组$f$维护栈$A$的前缀和的最大值即可。
对于$I\ x$
①把$x$入栈$A$
②更新

sum[A.size()] = sum[A.size() - 1] + A.top();

③更新

f[A.size()] = max(f[A.size() - 1],sum[A.size()])

对于$D$操作,把$A$的栈顶出栈

对于$L$操作,把$A$的栈顶弹到$B$中

对于$R$操作:
①把$B$的栈顶弹到$A$中
②更新

sum[A.size()] = sum[A.size() - 1] + A.top();

③更新

f[A.size()] = max(f[A.size() - 1],sum[A.size()])

对于询问,直接返回$f[k]$

代码

#include<cstdio>
#include<stack>
#include<cstring>
using std::stack;
inline int max(int a,int b){return a > b ? a : b;}
const int MAXN = (int)1e6 + 6;
int sum[MAXN],f[MAXN];
stack<int> A,B;

int main(){
    int Q,key;char op[MAXN];
    while(scanf("%d",&Q) != EOF){
        memset(sum,0,sizeof(sum));
        memset(f,0,sizeof(sum));
        f[0] = -0x7fffffff;
        while(A.size()) A.pop();
        while(B.size()) B.pop();
        while(Q--){
            scanf("%s",op);
            if(op[0] == 'I'){
                scanf("%d",&key);
                A.push(key);
                sum[A.size()] = sum[A.size() - 1] + A.top();
                f[A.size()] = max(f[A.size() - 1],sum[A.size()]);
            }else if(op[0] == 'D'){
                A.pop();
            }else if(op[0] == 'L'){
                if(!A.empty()) B.push(A.top()),A.pop();
            }else if(op[0] == 'R'){
                if(!B.empty()){
                    A.push(B.top());B.pop();
                    sum[A.size()] = sum[A.size() - 1] + A.top();
                    f[A.size()] = max(f[A.size() - 1],sum[A.size()]);   
                }
            }else if(op[0] == 'Q'){
                scanf("%d",&key);printf("%d\n",f[key]);
            }
        }
    }

    return 0;
}