Sample Input

8

I 2

I -1

I 1

Q 3

L

D

R

Q 2

Sample Output

2 3

发现IDLR四种操作都在光标处发生，且操作完成后光标至多移动1个位置，根据这种“始终在序列中间某个指定位置进行修改”的性质，我们不难想到一个类似对顶栈的做法A栈存储从序列开始到当前光标位置的子序列，B栈存储光标位置到结束的子序列，且二者都以光标所在的那一段为栈顶。k不超过光标，所以维护下A栈的前缀和最大值即可。 因为序列中有复数，f[0]初值不能是0，QaQ

#include 
        
         #define ll long longusing namespace std;const int N=1e6+100;const int inf=0x3f3f3f3f;stack
         
          A,B;int f[N],sum[N];char op;int n,x;int main(){    while (scanf("%d",&n)!=EOF)    {        memset(f,0,sizeof(f));        memset(sum,0,sizeof(f));        while (!A.empty()) A.pop();        while (!B.empty()) B.pop();        f[0]=-inf;        for (int i=1;i<=n;i++)        {            scanf(" %c",&op);            if (op=='I')            {                scanf("%d",&x);                A.push(x);                int m=A.size();                sum[m]=sum[m-1]+x;                f[m]=max(sum[m],f[m-1]);            }            else if (op=='L'&&!A.empty())            {                x=A.top();                A.pop();                B.push(x);            }            else if (op=='R'&&!B.empty())            {                x=B.top();                B.pop();                A.push(x);                int m=A.size();                sum[m]=sum[m-1]+x;                f[m]=max(sum[m],f[m-1]);            }            else if (op=='D')            {                if (!A.empty()) A.pop();            }            else if(op=='Q')            {                scanf("%d",&x);                printf("%d\n",f[x]);            }        }    }    return 0;}