AcWing 128. 编辑器（对顶栈 实现序列内部指定位置高效修改）

我们用这道题引入一个新的概念：对顶栈。（类似的，还有 对顶堆，日后我们会谈到）

思路：

本题的特殊点在于：I，D，L，R 四种操作 都在 光标位置处 发生，并且操作完成后，光标至多移动 1 个位置。

根据这种 “始终在 序列中间某个指定位置 进行 修改” 的性质，我们想到了 “对顶栈” 。

做法

建立两个栈：

• 栈 lestk 存储 从 序列开头 到 当前光标位置 的这一段子序列。

• 栈 ristk 存储 从 当前光标位置 到 序列结尾 的这一段子序列。

二者都以光标所在的那一端作为栈顶。这两个栈合起来就保存了整个序列。

因为 查询操作的 k不超过光标位置，所以我们用一个 数组 ans 维护栈 lestk 的 前缀和 的 最大值。

此外，设 lestk 的栈顶位置下标是 idx，sum 是序列 lestk 的前缀和数组。

（1）对于 I x 操作：

• 1.把 x 插入栈 lestk;
• 2.更新sum[idx] = sum[idx - 1] + lestk[idx];
• 3.更新ans[idx] = max(ans[idx - 1], sum[idx])。

（2）对于 D 操作，把 lestk 的栈顶出栈。

（3）对于 L 操作，弹出 lestk 的栈顶，插入到 ristk 中。

（4）对于 R 操作:

• 1.弹出 ristk 的栈顶，插入到 lestk 中;
• 2.更新sum[idx] = sum[idx - 1] + lestk[idx];
• 3.更新ans[idx] = max(ans[idx - 1], sum[idx])。

（5）对于 Q k 询问，直接返回 ans[k]。

通过这样两个 “对顶栈”，我们在 O(1) 的时间内 实现了每种操作和询问。

时间复杂度：

$O(1)$

代码：

#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;
}