Editor

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

2
3
Hint
The following diagram shows the status of sequence after each instruction:

 

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1000010;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
int mav[maxn<<2],st[maxn];
struct node
{
    int pre,next,rk,val,sum;
} pos[maxn];
void build(int L,int R,int rt)
{
    mav[rt]=-INF;
    if(L==R)
        return;
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    build(lson);
    build(rson);
}
void update(int L,int R,int rt,int p,int d)
{
    if(L==R)
    {
        mav[rt]=d;
        return;
    }
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
    if(p<=mid)
        update(lson,p,d);
    else
        update(rson,p,d);
    mav[rt]=max(mav[ls],mav[rs]);
}
int qu(int L,int R,int rt,int l,int r)
{
    if(l<=L&&R<=r)
        return mav[rt];
    int ls=rt<<1,rs=ls|1,mid=(L+R)>>1,tp=-INF;
    if(l<=mid)
        tp=max(tp,qu(lson,l,r));
    if(r>mid)
        tp=max(tp,qu(rson,l,r));
    return tp;
}
int main()
{
    int q,i,x,ps,ns,tot;
    char cmd[10];

    while(~scanf("%d",&q))
    {
        tot=0;
        build(1,q,1);
        for(i=q+5;i>=0;i--)
            st[tot++]=i;
        ps=st[--tot];
        pos[ps].pre=pos[ps].next=-1;
        pos[ps].rk=pos[ps].sum=0;
        for(i=1;i<=q;i++)
        {
            scanf("%s",cmd);
            if(cmd[0]=='I')
            {
                scanf("%d",&x);
                ns=st[--tot];
                pos[ns].val=x;
                pos[ns].rk=pos[ps].rk+1;
                pos[ns].sum=pos[ps].sum+x;
                pos[ns].pre=ps;
                pos[ns].next=pos[ps].next;
                if(pos[ps].next!=-1)
                    pos[pos[ps].next].pre=ns;
                pos[ps].next=ns;
                update(1,q,1,pos[ns].rk,pos[ns].sum);
                ps=ns;
            }
            else if(cmd[0]=='D')
            {
                if(pos[ps].pre==-1)
                    continue;
                pos[pos[ps].pre].next=pos[ps].next;
                if(pos[ps].next!=-1)
                    pos[pos[ps].next].pre=pos[ps].pre;
                st[tot++]=ps;
                ps=pos[ps].pre;
            }
            else if(cmd[0]=='L')
            {
                if(pos[ps].pre!=-1)
                    ps=pos[ps].pre;
            }
            else if(cmd[0]=='R')
            {
                if(pos[ps].next==-1)
                    continue;
                pos[pos[ps].next].rk=pos[ps].rk+1;
                pos[pos[ps].next].sum=pos[ps].sum+pos[pos[ps].next].val;
                ps=pos[ps].next;
                update(1,q,1,pos[ps].rk,pos[ps].sum);
            }
            else
            {
                scanf("%d",&x);
                printf("%d\n",qu(1,q,1,1,x));
            }
            //printf("ps %d\n",pos[ps].rk);
        }
    }
    return 0;
}