[P2201 数列编辑器 // HDU-4699 Editor] 题解

lougu 看不到，遂写博客

题目描述

小 Z 是一个爱好数学的小学生。最近，他在研究一些关于整数数列的性质。为了方便他的研究，小 Z 希望实现一个叫做 "Open Continuous Lines Processor" 的数列编辑器。

一开始，数列编辑器里没有数字，只有一个光标。这个数列编辑器需要支持五种操作。

• I x 在当前光标前插入数字 \(x\)。
• D 删除当前光标前的数字。
• L 光标向前移动一个数字。
• R 光标向后移动一个数字。
• Q k 设光标之前的数列是 \(\{a_1,a_2,\cdots,a_n\}\)，输出第 \(k\) 位及之前最大的前缀和，保证 \(k\leq n\)。

输入格式

第一行包含一个数字 \(N\)，表示操作的个数。接下来包含 \(N\) 行，每行包含一条命令。

输出格式

对于每个 Q k 命令，输出一个整数表示这个操作的答案。

---

• 对于 \(50\%\) 的数据，\(N\leq 10^3\)；
• 对于 \(80\%\) 的数据，\(N\leq 10^5\)；
• 对于 \(100\%\) 的数据，\(N\leq 10^6\)，插入的数字绝对值大小不会超过 \(10^3\)。
• 题目保证不会在数列编辑器为空时进行 D 操作。

---

解析

本题数据范围只有最后 \(20\%\) 比较难做。

\(80\% \space \text{pts}\) 做法

模拟做法，不用计算每个前缀和，直接用栈维护（用数组也可以模拟），注意指针位置。

...
#define endl '\n'
using namespace std;
using ll = long long;
ll N, x, array[1000005], q=0, ptr=0; // array 为模拟的栈
char opr;ll calpref(ll k){ // 计算前缀和ll prefix_sum = 0, max_sum = -LLONG_MAX;for (int i=1; i<=k; ++i) {prefix_sum += array[i];max_sum = max(max_sum, prefix_sum); // 不全部计算，而是遍历列表，把已经求出来的前缀和和当前最大比较}return max_sum;
}int main(void){ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);memset(array, 0, sizeof array);// 常规卡常cin >> N;while(N--){cin >> opr;if(opr == 'I' || opr == 'Q')cin >> x;if(opr == 'I'){if(ptr != q)for (int i=q; i>ptr; --i) array[i+1] = array[i];// 注意插入元素需要把整体元素向右移动array[++ptr] = x;q++;}else if(opr == 'D'){if(ptr != q)for(int i=ptr; i<q; ++i)array[i] = array[i+1];// 注意删除元素需要把整体元素向左移动ptr--;--q;}else if(opr == 'L'){ // 左移ptr--;}else if(opr == 'R'){ // 右移ptr++;}else if(opr == 'Q'){ll res = calpref(x);cout << res << endl;continue;}}return 0;
}

\(80\space \text{pts}\) 拿到。

\(100\% \space \text{pts}\) 做法

使用对顶栈思想维护，当插入的时候，左栈 \(L\) 增加元素；向左时，左栈 \(L\) 栈顶元素成为右栈 \(R\) 栈顶元素，反之亦然；删除时，删除左栈的栈顶。对于前缀和最大值，另开数组记录。如果左侧栈有改变，修改最大值和前缀和数组。

...
#define endl '\n'
using namespace std;
using ll = long long;
ll N, x, diff[1000005], mx[1000005]; // 前缀和数组和最大前缀和数组
char opr;
stack<ll> L, R; // 左栈和右栈int main(void){memset(diff, 0, sizeof diff);memset(mx, 0, sizeof mx); // 长度为 0 的最大前缀和为 0mx[0] = -LLONG_MAX;cin >> N;for(int i=1; i<=N; ++i){cin >> opr;if(opr == 'I' || opr == 'Q'){cin >> x;if(opr == 'I'){L.push(x); // 插入元素const ll l = L.size();diff[l] = diff[l-1] + L.top(); // 更新前缀和数组mx[l] = max(diff[l], mx[l-1]); // 更新最大前缀和数组}else if(opr == 'Q') cout << mx[x] << endl; // 输出}else{if(opr == 'L' && !L.empty()){R.push(L.top()); // 向左走，R栈顶变为L的栈顶，前缀和数组不变，前缀和最大值数组也不变L.pop();}else if(opr == 'R' && !R.empty()){L.push(R.top()); // 向右走，L栈顶变为R的栈顶R.pop();const ll l = L.size();diff[l] = diff[l-1] + L.top();mx[l] = max(diff[l], mx[l-1]);// 前缀和数组更新，前缀和最大值数组更新}else if(opr == 'D')L.pop(); // 删除元素}}return 0;
}

return 0;