AcWing 128. Editor (to effectively modify the specified position in the top stack)

We use this problem to introduce a new concept ： The top of the stack .（ Allied , also To the top pile , We will talk about ）

Ideas ：

The special point of this question is ：I,D,L,R Four operations All in At the cursor position happen , And when it's done , The cursor moves at most 1 A place .

According to this “ Always in A specified position in the middle of the sequence Conduct modify ” The nature of , We thought about it “ The top of the stack ” .

practice

Set up two stacks ：

• Stack lestk Storage from The beginning of the sequence To Current cursor position This sub sequence of .

• Stack ristk Storage from Current cursor position To End of sequence This sub sequence of .

Both use the end of the cursor as the top of the stack . Together, these two stacks save the entire sequence .

because Query operation k Do not exceed the cursor position , So we use a Array ans Maintenance stack lestk Of The prefix and Of Maximum .

Besides , set up lestk The subscript at the top of the stack is idx,sum It's a sequence lestk Prefix and array .

（1） about I x operation ：

• 1. hold x Insert stack lestk;
• 2. to update sum[idx] = sum[idx - 1] + lestk[idx];
• 3. to update ans[idx] = max(ans[idx - 1], sum[idx]).

（2） about D operation , hold lestk Top stack of .

（3） about L operation , eject lestk Top of stack , Insert into ristk in .

（4） about R operation :

• 1. eject ristk Top of stack , Insert into lestk in ;
• 2. to update sum[idx] = sum[idx - 1] + lestk[idx];
• 3. to update ans[idx] = max(ans[idx - 1], sum[idx]).

（5） about Q k inquiry , Go straight back to ans[k].

Through these two “ The top of the stack ”, We are O(1) In time Each operation and inquiry is realized .

Time complexity ：

$O(1)$

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
stack<int> lestk, ristk;
int sum[N];
int ans[N];

int main()
{
    
	int T = 1; //cin >> T;

	while (T--)
	{
    
		memset(ans, -0x3f, sizeof ans);
		int q; cin >> q;
		int idx = 0;
		while (q--)
		{
    
			char op[2];
			cin >> op;
			
			if (*op == 'I') {
    
				int x; cin >> x;
				idx++;
				lestk.push(x);
				sum[idx] = sum[idx - 1] + x;
				//cout << "sum[idx] idx " << sum[idx] << ' ' << idx << endl;
				ans[idx] = max(ans[idx - 1], sum[idx]);
			}
			else if (*op == 'D') {
    
				if (lestk.size()) {
    
					sum[idx] -= lestk.top();
					ans[idx] = max(ans[idx - 1], sum[idx]);
					idx--;
					lestk.pop();
				}
			}
			else if (*op == 'L') {
    
				
				if (lestk.size()) {
    
					idx--;
					int top = lestk.top();
					lestk.pop();
					ristk.push(top);
				}
			}
			else if (*op == 'R') {
    

				if (ristk.size()) {
    
					idx++;
					
					int top = ristk.top();
					sum[idx] = sum[idx - 1] + top;
					ans[idx] = max(ans[idx - 1], sum[idx]);
					ristk.pop();
					lestk.push(top);
				}
			}
			else if (*op == 'Q') {
    
				int k; cin >> k;
				cout << ans[k] << '\n';
			}
		}
	}

	return 0;
}