數列編輯器

數 列 編 輯 器 數列編輯器 數列編輯器

題目連結：luogu P2201 / jzoj 3922

題目

小 Z Z Z是一個愛好數學的國小生。最近，他在研究一些關于整數數列的性質。

為了友善他的研究，小 Z Z Z希望實作一個叫做 “ O p e n   C o n t i n u o u s   L i n e s   P r o c e s s o r ” “Open\ Continuous\ Lines\ Processor” “Open Continuous Lines Processor”的數列編輯器。

一開始，數列編輯器裡沒有數字，隻有一個光标。這個數列編輯器需要支援五種操作。

1. I   x I\ x I x 在目前光标前插入數字 x x x。
2. D D D 删除目前光标前的數字。
3. L L L 光标向前移動一個數字。
4. R R R 光标向後移動一個數字。
5. Q   k Q\ k Q k 設光标之前的數列是 { a 1 ， a 2 ， … … ， a n } \{a1，a2，……，an\} {a1，a2，……，an}，輸出第 k k k位及之前最大的字首和，保證 k ≤ n k≤n k≤n。

輸入

第一行包含一個數字 N N N ，表示操作的個數。

接下來包含 N N N 行，每行包含一條指令。

輸出

對于每個 Q   k Q\ k Q k 指令，輸出一個整數表示這個操作的答案。

樣例輸入

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

樣例輸出

2
3
           

資料範圍

對于 50 % 50\% 50% 的資料， N ≤ 1000 N ≤ 1000 N≤1000；

對于 80 % 80\% 80% 的資料， N ≤ 100000 N ≤ 100000 N≤100000；

對于 100 % 100\% 100% 的資料， N ≤ 1000000 N ≤ 1000000 N≤1000000，插入的數字絕對值大小不會超過 1000 1000 1000。

思路

這道題就是一道大模拟題。

因為題目問的隻有光标前面的數字，是以我們可以弄兩個棧，一個正序儲存光标前面的數字，一個倒序儲存光标後面的數字。

然後我們隻要維護前面的棧的字首和和答案，其它操作時做對應的操作，最後題目要求輸出時直接輸出答案就可以了。

代碼

#include<cstdio>
#include<iostream>
#define rr register 

using namespace std;

int a[1000001], b[1000001], ans[1000001], q[1000001], t1, t2, n;

int main() {
    scanf("%d", &n);//讀入
    
    ans[0] = -2147483647;//初始化
    for (rr int i = 1; i <= n; i++) {
    	char c;
    	c = getchar();//讀入
    	while (c < 'A' || c > 'Z') c = getchar();//處理換行符等其它字元
        if (c == 'I') {
            int x;
			scanf("%d", &x);//讀入
            a[++t1] = x;//插入
            q[t1] = q[t1 - 1] + x;//字首和
            ans[t1] = max(ans[t1 - 1], q[t1]);//答案
        }
        if (c == 'D') {
			t1--;//删除
        }
        if(c == 'L') {
			b[++t2] = a[t1--];//移動光标左邊最右邊的一個數到光标右邊的第一個
        }
        if(c == 'R') {
            int x = b[t2--];//取出光标右邊的第一個數字
            a[++t1] = x;//放到光标左邊的最後
            q[t1] = q[t1 - 1] + x;//字首和
            ans[t1] = max(ans[t1 - 1], q[t1]);//答案
        }
        if(c == 'Q') {
            int x;
			scanf("%d", &x);//讀入
            printf("%d\n", ans[x]);//直接輸出答案
        }
    }
    
    return 0;
}