(Sky OJ) 129. Day 1 PG. 日月卦長的編輯器

https://pc2.tfcis.org/sky/index.php/problem/view/129/

要想辦法 O(N) 喔~

#include <iostream>
#include <stdio.h>
#include <cassert>
using namespace std;

const int MAX_N = 1e6 + 6;

int mx[MAX_N],pre[MAX_N],tag[MAX_N],lc[MAX_N],rc[MAX_N],val[MAX_N];
int ans[MAX_N];

int main () {
    int q;
    scanf("%d",&q);
    int id=1;
//    int sz=0;
    int nowL=0;
    int nowR=0;
    int ans_id = 0;
    while (q--) {
        getchar();
        char c;
        scanf("%c",&c);
        if (c=='I') {
            int x;
            scanf("%d",&x);
            if (nowL==0) {
                rc[id] = nowR;
                lc[id] = nowL;
                pre[id] = x;
                mx[id] = x;
                tag[id] = 0;
                if (nowR != 0) {
                    lc[nowR] = id;
                    tag[nowR] += x;
                    pre[nowR] += x;
                    mx[nowR] = max(mx[nowL],pre[nowR]); 
                }
                nowL = id;
            }
            else {
                rc[id] = nowR;
                lc[id] = nowL;
                rc[nowL] = id;
                assert(tag[nowL] == 0);
                pre[id] = pre[nowL] + x;
                mx[id] = max(mx[nowL],pre[id]);
                tag[id]=0;
                if (nowR != 0) {
                    lc[nowR] = id;
                    tag[nowR] += x;
                    pre[nowR] += x;
                    mx[nowR] = max(mx[id],pre[nowR]); 
                }
                nowL = id;
            }
            ans[++ans_id] = mx[id];
            val[id] = x;
            id++;
        }
        else if (c=='D') {
            if (lc[nowL] != 0)rc[lc[nowL]] = nowR;
            if (nowR == 0) {
                nowL = lc[nowL];
                ans_id--;
                continue;
            }
            lc[nowR] = lc[nowL];
            tag[nowR] -= val[nowL];
            pre[nowR] -= val[nowL];
            nowL = lc[nowL];
            mx[nowR] = max(mx[nowL],pre[nowR]);
            ans_id--;
        }
        else if (c=='R') {
            if (nowR != 0) {
                if (nowL != 0) {
                    tag[nowR] += tag[nowL];
                    pre[nowR] += tag[nowL];
                    mx[nowR] = max(mx[nowL],pre[nowR]);
                    tag[nowL] = 0;    
                }
                nowL = nowR;
                nowR = rc[nowR];
                if (nowL != 0) {
                    tag[nowR] += tag[nowL];
                    pre[nowR] += tag[nowL];
                    mx[nowR] = max(mx[nowL],pre[nowR]);
                    tag[nowL] = 0;    
                }
                ans[++ans_id] = mx[nowL];
            }
        }
        else if (c=='L') {
            if (nowL != 0) {
                nowR = nowL;
                nowL = lc[nowL];
                --ans_id;
            }
        }
        else if (c=='Q'){
            int k;
            scanf("%d",&k);
//            assert(ans_id >= k);
            printf("%d\n",ans[k]);
        }
    }
}