前言
这下又不是官解了吧？
模拟赛题，在一个月后又出现在了数据结构讲稿上，令人忍俊不禁。
Solution
官方解法是用线段树加矩阵，不过赛时的我显然没这么聪明，是想不到的。
赛时我就只知道先发掘一些答案的性质。
一、一些性质
首先，发现这个撤销操作比较棘手，考虑没有撤销操作的情况下，每一个新的操作对答案的贡献。
发现：对于每次操作二，对答案的贡献绝对只有 \(1\)！
只是在开头结尾各自加上一个括号，从左括号 \(+1\)、右括号 \(-1\) 来看，前缀数组是时刻 \(\ge0\) 的，如果在开头结尾加上一个括号，那前缀数组就只有最后一位为 \(0\)，也就是以第一个括号开头只能匹配结尾括号，反之亦然。
类似的，考虑操作一在结尾加上一组括号，增加的贡献一定是以最后括号结尾的，此时
(......)(......)(......) + ()
前面有几组括号贡献就是组数 \(+1\)，例如上图中尾部加入括号，贡献为 \(4\)。
换句话说，操作二贡献恒为 \(1\)，操作一贡献取决于前面连续操作一的次数，贡献为连续次数 \(+1\)。
有一种 OSU! 的美。
二、如何维护
你以为这道题就做完了？撤销操作才是本题的重点！
考虑撤销操作可能会对连续操作一的长度有影响。
比如说：
2 1 1 1 1 2 1 1 1
撤销掉第二个操作二，会导致其左右两边操作一连起来。
就像打音游，本来某个位置一直断，有一次这里全连了，最后连击数就会变高。
而且还可以撤销撤销操作，就导致已经被撤销的操作二可能会打赢复活赛。
换句话说我们得维护一个关于操作二的链表，能支持随时在某个位置插入，删除和查询前面或者后面的第一个操作二。
但是直接写链表，操作一怎么办？
因为我们还需要能够快速得出两个位置之间的操作一次数，这是一个区间查询，链表上显然行不通。
但是偶然间想到一个复杂度稍逊但是也可以维护链表的东西：平衡树！
这道题的解法就显然了：
用 set 维护操作二的插入和删除，记录下每次操作二的位置之后，便可以用树状数组来查询其间操作一数量。
三、具体影响
末尾加操作二，简单，\(+1\) 即可。
末尾加操作一，用 set 找到上一个还活着的操作二，树状数组求出其间的操作一数量为 \(x\) 贡献为 \(x+1\)。
中间插入或删除操作一：找到左右的操作二，剩下同上。
中间插入或删除操作二，看看这个操作二左右两端各有多长的操作一，简单计算即可。
复杂度显然为 \(O(n\log n)\)。
这显然不是官方解法，而且显然比官方做法简单。
AC 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t[1234657],n,cnt;
void change(int x,int v)
{
for(;x<=n+10;x+=x&-x) t[x]+=v;
}
int ask(int x)
{
int ans=0;
for(;x>0;x-=x&-x) ans+=t[x];
return ans;
}
set<int> s,fs;
int i,j,op,x;
int ot[666666],ch[666666],lo[666666];
signed main()
{
cin>>n;
for(i=1;i<=n;i++)
ch[i]=i;
int ans=1,p=1;
s.insert(0);fs.insert(0);
s.insert(n+1);fs.insert(-n-1);
for(i=1;i<=n;i++)
{
cin>>op;
ot[i]=op;
if(op==1)
{
cnt++;
lo[i]=cnt;
change(cnt,1);
int q=-(*fs.upper_bound(-cnt));
ans+=ask(cnt)-ask(q)+1;
}
if(op==2)
{
ans++;
cnt++;
lo[i]=cnt;
s.insert(cnt);fs.insert(-cnt);
}
if(op==3)
{
cin>>x;
ch[i]=-ch[x];
if(ch[i]>0)
{
int ty=ot[ch[i]],loc=lo[ch[i]];
int fr=-(*fs.upper_bound(-loc)),bk=*s.upper_bound(loc);
if(ty==1)
{
change(loc,1);
ans+=ask(bk-1)-ask(fr)+1;
}
if(ty==2)
{
s.insert(loc);fs.insert(-loc);
ans++;
int c=ask(bk-1)-ask(fr);
ans-=c*(c+3)/2;
c=ask(loc-1)-ask(fr);
ans+=c*(c+3)/2;
c=ask(bk-1)-ask(loc);
ans+=c*(c+3)/2;
}
}
else
{
int ty=ot[-ch[i]],loc=lo[-ch[i]];
int fr=-*fs.upper_bound(-loc),bk=*s.upper_bound(loc);
if(ty==1)
{
change(loc,-1);
ans-=ask(bk-1)-ask(fr)+2;
}
if(ty==2)
{
ans--;
s.erase(loc);fs.erase(-loc);
int c=ask(bk-1)-ask(fr);
ans+=c*(c+3)/2;
c=ask(loc-1)-ask(fr);
ans-=c*(c+3)/2;
c=ask(bk-1)-ask(loc);
ans-=c*(c+3)/2;
}
}
}
cout<<ans<<endl;
}
return 0;
}
后记
这题解有一种为了一碗醋包了一盘饺子的美。
什么叫数据结构只会树状数组啊。