题解 P1503 【鬼子进村】
wuzhoupei
2018-01-25 16:35:27
上面是我的 Logo >\_<
~~这个我不会用平衡树，线段树之类的搞~~
我一开始想平衡树了，fhq Treap
但是我是真心没想到怎么操作
根据某白的话
>遇事不决先分块
所以
我用的分块啊
简单暴力 而且稳定O(nsqrt(n))
超级棒
```cpp
#include <bits/stdc++.h>
#define II int
#define IL inline
#define R register
#define I 123456
using namespace std;
IL void of(R II &a) {
R char c=getchar(); R II w=1,p=0;
while (c<'0' || c>'9') { if(c=='-') w=-1; c=getchar(); }
while (c>='0' && c<='9') { p=p*10+c-'0'; c=getchar(); }
a=p*w;
}
/* -------------------- Peipei -------------------- */
II Stack[I], had[I], lazy[I], belong[I];
II block,n,m,_top;
IL II Ll(R II x) {
R II ans=0;
while (x>0 && !lazy[x/block]) ans+=min(x,block), x-=block;
while (x>0 && !had[x]) ans++, x--;
return ans;
}
IL II Rr(R II x) {
R II ans=0; if(x==n+1) return 0;
while (x<=n && !lazy[belong[x]]) ans+=block, x+=block;
if(x>n+1) ans-=block-(n-n/block*block);
while (x<=n && !had[x]) ans++, x++;
return ans;
}
IL II todo(R II x) {
R II ans=0,l=x,r=x,flag=0;
if(had[x]) return 0;
while (l && belong[l]==belong[x]) {
ans++; l--;
if(had[l]) { flag=1; break ; }
}
if(!flag) ans+=Ll(l);
flag=0;
r++;
while (r<=n && belong[r]==belong[x]) {
if(had[r]) { flag=1; break ; }
ans++; r++;
}
if(!flag) ans+=Rr(r);
return ans;
}
int main()
{
// freopen("1.in","r",stdin);
of(n); of(m); block=sqrt(n);
for(R II i=1;i<=n;i++) belong[i]=(i-1)/block+1;
R char opt; R II x;
while (m --) {
cin>> opt;
if(opt=='D') {
of(x); Stack[++_top]=x;
had[x]=1;
lazy[belong[x]]++;
}
if(opt=='R') {
x=Stack[_top--];
had[x]=0;
lazy[belong[x]]--;
}
if(opt=='Q') {
of(x);
printf("%d\n",todo(x));
}
}
}
```
根本不用去讲细节实现
裸的分块啦