题目背景
小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。
题目描述
描述 县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来
1、消息为D x：鬼子将x号房子摧毁了，地道被堵上。
2、消息为R ：村民们将鬼子上一个摧毁的房子修复了。
3、消息为Q x：有一名士兵被围堵在x号房子中。
李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。
输入输出格式
输入格式：
第一行2个整数n，m（n，m<=50000）。
接下来m行，有如题目所说的三种信息共m条。
输出格式：
对于每一个被围堵的士兵，输出该士兵能够到达的房子数。
输入输出样例
输入样例#1：
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4
输出样例#1：
1
0
2
4
说明
若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。
有人暴力AC！！！
//80‘
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int cnt=;
char s;
int sum;
int xxx[];
int n,m;
int f[]={};
void sousuo2(int a)
{
if(f[a]||a==) return;
if(f[a]==)
{
sum++;
sousuo2(--a);
}
}
void sousuo(int x,int y)
{
if(f[x]||x>n)
{
sousuo2(y-);
return;
}
if(f[x]==)
{
sum++;
sousuo(++x,y);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
cin>>s;
if(s=='D')
{
scanf("%d",&xxx[++cnt]);
f[xxx[cnt]]=;
}
if(s=='Q')
{
int x;
sum=;
scanf("%d",&x);
int y=x;
if(f[x]==)
sum=;
else
sousuo(x,y);
printf("%d\n",sum);
}
if(s=='R')
f[xxx[cnt--]]=;
}
return ;
}
//100——by whw
//我太懒了
#include<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define M 50001
using namespace std;
stack<int> q;
bool vis[M];
int tree[M];
int a[M],n,m;
inline int read(int&x) {
x=;char c=getchar();
while(c>''||c<'') c=getchar();
while(c>=''&&c<='') x=*x+c-,c=getchar();
}
int main() {
read(n);read(m);
char s;
int x,bj=,tot=;
for(int i=;i<=n;i++) vis[i]=true;
for(int i=;i<=m;i++) {
cin>>s;
if(s=='D') {
read(x);
q.push(x);
vis[x]=false;
a[++tot]=x;
}
else if(s=='R') {
x=q.top();
q.pop();
vis[x]=true;
sort(a+,a+tot+);
for(int i=;i<=tot;i++)
if(a[i]==x) {
if(a[i]==a[tot]) tot--;
else a[i]=a[tot],tot--;
break;
}
}
else if(s=='Q') {
read(x);
if(!vis[x]) printf("0\n");
else {
sort(a+,a+tot+);
if(x>a[tot]) printf("%d\n",n-a[tot]);
else for(int i=;i<=tot;i++) {
if(a[i]>x) {
printf("%d\n",a[i]-a[i-]-);
break;
}
}
}
}
}
return ;
}