分析
分块。
我们定义 \(\mathit{cnt}_i\) 表示房子 \(i\) 是否出现过，\(\mathit{sum}_i\) 表示在第 \(i\) 个块内没有被摧毁的房子数量，维护的房子是 \((i-1)\times S-1\) 到 \(i \times S\)，其中 \(S=\sqrt{n}\) 也就是块长。
操作 \(1\)。写一个栈，根据后进先出的特点，讲摧毁的房子 \(x\) 入栈，以便后面修复。将 \(\mathit{cnt}_x\) 与 \(x\) 对应块的 \(\mathit{sum}\) 减 \(1\) 即可。
操作 \(2\)。先从栈里找到被修复的房子 \(x\)。与操作 \(1\) 同理，将减 \(1\) 变成加 \(1\) 即可。
操作 \(3\)。对于 \(x\) 能走到的房子，一定是在 \([l,r]\) 满足 \(\sum\limits_{i=l}^r \mathit{cnt}_i =(r-l+1)\) 的情况下的最大区间。我们可以分开来求。对于暴力，我们从 \(x\) 开始一直走，直到某一个 \(\mathit{cnt}_i=0\) 为止，能证明这是最大区间的 \(l\)。\(r\) 同理，不在此赘述。考虑优化，我们可以先找到 \(x\) 所在的块 \(k_x\)，暴力求 \(k_x\) 中的贡献，再对于整块求贡献，最后对于不完整的块（答案边界）暴力。这里需要特别对 \(k_x=k_n\) 进行判断，因为 \(k_n \times S\) 可能大于 \(n\)，即最后一个块不完整。这时候直接暴力。由于我们是分开求 \(l,r\) 两边的贡献的，这时候在 \(\mathit{cnt}_x=1\) 的情况会将 \(x\) 的贡献重复加 \(1\) 遍，所以要对贡献和减 \(1\)。
复杂度是 \(O(n\sqrt{n})\) 的。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
const int N=5e4+10;
int cnt[N],sum[N],block,len;
int n,m;
int st[N],tt;
il int get(int x){return (x-1)/len+1;}
il int findl(int x){
block=get(x);
int ans=0;
for(re int i=x;i>=((block-1)*len)+1;--i)
if(!cnt[i]) return ans;
else ans++;
--block;
for(;block>=1;--block)
if(sum[block]==len) ans+=len;
else for(re int i=block*len;i>=((block-1)*len)+1;--i)
if(!cnt[i]) return ans;
else ans++;
return ans;
}
il int findr(int x){
int maxx=get(n);
block=get(x);
int ans=0;
for(re int i=x;i<=block*len&&i<=n;++i)
if(!cnt[i]) return ans;
else ans++;
++block;
for(;block<maxx;++block)
if(sum[block]==len) ans+=len;
else for(re int i=(block-1)*len+1;i<=block*len;++i)
if(!cnt[i]) return ans;
else ans++;
for(re int i=(block-1)*len+1;i<=n;++i)
if(!cnt[i]) return ans;
else ans++;
return ans;
}
il void solve(){
cin>>n>>m;len=sqrt(n);
for(re int i=1;i<=n;++i) ++cnt[i],++sum[get(i)];
for(re int i=1;i<=m;++i){
char op;int x,now;cin>>op;
if(op=='D') cin>>x,st[++tt]=x,--cnt[x],--sum[get(x)];
else if(op=='R') now=st[tt--],++cnt[now],++sum[get(now)];
else cin>>x,cout<<((!cnt[x])?0:findl(x)+findr(x)-1)<<"\n";
}
return ;
}
signed main(){
solve();
return 0;
}