【套路数据结构】CF1858E2 Rollbacks (Hard Version)
CSP_Sept
·
·
题解
题意
维护一个初始为空的序列 a，支持以下操作：
## 解法
**本题解含有 $O(q\log q)$ 做法与 $O(q)$ 做法。**
经典地，我们用 set 维护所有数字的出现的所有位置，更新时只需要查询其首位即可。
这样我们可以轻松实现 $\texttt +$ 操作。
为了实现 $\texttt -$ 操作，我们引入序列 $A$，使得序列 $A$ 的前 $l$ 位恰好为序列 $a$（$l$ 为序列 $a$ 此时的长度）。这样一来，我们更新时直接将 $l$ 更改为 $l-k$ 即可。
这样做同样是为了方便进行 $\texttt !$ 操作。因为我们实际上保留了 $1\sim l_{\max}$ 的所有信息，足以进行回溯。
对于 $\texttt !$ 操作，我们使用 stack 存储所有操作，并尝试逆向地进行还原，具体情况与上面的 $\texttt +/\texttt -$ 操作思路一致。
**特别地，对于 $\texttt +$ 操作，我们需要存储原来的 $A_{l'}$ 而不是 $x$。这是容易理解的。**
至于答案的更新，我们在所有元素**第一次出现的位置**标记为 $1$，这个是已经维护过的。
那么 $\texttt ?$ 操作只需要输出该数组在 $[1,l]$ 上的区间和即可。
至此，我们需要一个可以支持单点修改、查询区间和的数据结构。拉一个树状数组即可。
时间复杂度 $O(q\log q)$。
## 代码
```cpp
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <cstring>
#define N 1000010
#define M 1000000
#define ll long long
using namespace std;
inline ll rd(){
char c;
bool flag = 0;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = 1;
ll res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + c - '0';
return flag ? -res : res;
}
int q, l = 0;
int a[N], c[N];
set <int> s[N];
void add(int x, int y){
for( ; x <= M ; x += x & -x) c[x] += y;
}
int query(int x){
int ans = 0;
for( ; x ; x -= x & -x) ans += c[x];
return ans;
}
struct lst{
int st, x;
};
lst init(char op, int x){
lst t;
t.st = (op == '+'), t.x = x;
return t;
}
vector <lst> oper;
int main(){
memset(a, -1, sizeof(a));
q = rd();
while(q--){
char op; int x;
scanf("\n%c", &op);
if(op == '+'){
x = rd(); ++l;
if(a[l] != -1){
if(s[a[l]].size()){
add(*s[a[l]].begin(), -1);
s[a[l]].erase(l);
}
if(s[a[l]].size()) add(*s[a[l]].begin(), 1);
}
oper.push_back(init(op, a[l]));
a[l] = x;
if(x != -1){
if(s[x].size()) add(*s[x].begin(), -1);
s[x].insert(l);
add(*s[x].begin(), 1);
}
}
else if(op == '-'){
x = rd(); l -= x;
oper.push_back(init(op, x));
}
else if(op == '?'){
printf("%d\n", query(l));
fflush(stdout);
}
else{
lst last_alt = oper.back(); oper.pop_back();
if(last_alt.st){
int t = last_alt.x;
if(a[l] != -1){
if(s[a[l]].size()){
add(*s[a[l]].begin(), -1);
s[a[l]].erase(l);
}
if(s[a[l]].size()) add(*s[a[l]].begin(), 1);
}
a[l] = t;
if(t != -1){
if(s[t].size()) add(*s[t].begin(), -1);
s[t].insert(l);
if(s[t].size()) add(*s[t].begin(), 1);
}
--l;
}
else l += last_alt.x;
}
}
return 0;
}
```
## 优化
虽然上述代码已经可以通过，但是考虑优化之。
逐个解决瓶颈：
- **树状数组**：可以用前缀和替代。容易发现是可行的；
- **维护各个元素出现的位置**：我们发现改变一个元素第一次出现的位置，必然伴随着一个当前已知位置该元素的更新或该元素的彻底删除。据此可以只用一个数组 $pos$ 代替上述题解中提出的 set 进行维护。
据此，我们得到时间复杂度 $O(q)$ 的做法。代码从略。
___
**2023.08.17** 修正一处笔误。