Description

你正在設(shè)計(jì)一種新型的編輯器，這種編輯器可以高效地處理整數(shù)序列。
編輯器啟動(dòng)時(shí)，序列為空，光標(biāo)指向序列的頭部。編輯器支持下列 5 種操作：
1. I x 把整數(shù) x 插入到光標(biāo)位置；
2. D 刪除光標(biāo)之前的整數(shù)（保證光標(biāo)不在序列的頭部）；
3. L 如果光標(biāo)不在序列的頭部，向左移動(dòng)一個(gè)位置，否則不移動(dòng)；
4. R 如果光標(biāo)不在序列的尾部，向右移動(dòng)一個(gè)位置，否則不移動(dòng)；
5. Q k 假設(shè)光標(biāo)之前的序列是 {a1, a2, … , an}，求 S1, S2, … , Sk 的最大值（其中 Si = a1 +a2 +· · ·+ai ）。保證 k ≤ n。

Input

第 1 行，1 個(gè)整數(shù) Q，表示操作的數(shù)量。
接下來(lái) Q 行，每行描述一個(gè)操作。

Output

對(duì)于每個(gè)操作 Q，輸出對(duì)應(yīng)的最大值。

Sample Input

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

Sample Output

2
3

Data Constraint

? 對(duì)于 30% 的數(shù)據(jù)，Q ≤ 1000；
? 對(duì)于 60% 的數(shù)據(jù)，Q ≤ 10^5；
? 對(duì)于 100% 的數(shù)據(jù)，1 ≤ Q ≤ 10^6, |x| ≤ 1000。

Solution

• 用兩個(gè)棧分別維護(hù)光標(biāo)兩邊的數(shù)，如光標(biāo)右移就將右邊的棧頂元素彈出再加入左邊的棧頂。

• 記得判斷棧為空則不彈棧（光標(biāo)到邊界了）。

• 然后維護(hù)左邊棧的前綴和 和 前綴和的最大值，移光標(biāo)時(shí)修改即可。

• 這樣就可以做到線性復(fù)雜度 O(Q) 。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=1e6+5; int n1,n2,sum; int a[N],b[N],ans[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0'); } inline void change(int x) {sum+=a[++n1]=x;ans[n1]=ans[n1-1]>sum?ans[n1-1]:sum; } int main() {int q=read();ans[0]=-1e9;while(q--){char ch=getchar();while(ch^'I' && ch^'Q' && ch^'L' && ch^'R' && ch^'D') ch=getchar();if(ch=='I') change(read()); elseif(ch=='Q') write(ans[read()]),putchar('\n'); elseif(ch=='L'){if(n1) sum-=a[n1],b[++n2]=a[n1--];}elseif(ch=='R'){if(n2) change(b[n2--]);}else sum-=a[n1--];}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 3789. 【NOI2015模拟8.20】编辑器的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。