题目背景
小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。
题目描述
描述 县城里有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=0; char s; int sum; int xxx[50010]; int n,m; int f[50010]={0}; void sousuo2(int a) { if(f[a]||a==0) return; if(f[a]==0) { sum++; sousuo2(--a); } } void sousuo(int x,int y) { if(f[x]||x>n) { sousuo2(y-1); return; } if(f[x]==0) { sum++; sousuo(++x,y); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { cin>>s; if(s=='D') { scanf("%d",&xxx[++cnt]); f[xxx[cnt]]=1; } if(s=='Q') { int x; sum=0; scanf("%d",&x); int y=x; if(f[x]==1) sum=0; else sousuo(x,y); printf("%d ",sum); } if(s=='R') f[xxx[cnt--]]=0; } return 0; }
//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=0;char c=getchar(); while(c>'9'||c<'0') c=getchar(); while(c>='0'&&c<='9') x=10*x+c-48,c=getchar(); } int main() { read(n);read(m); char s; int x,bj=0,tot=0; for(int i=1;i<=n;i++) vis[i]=true; for(int i=1;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+1,a+tot+1); for(int i=1;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 "); else { sort(a+1,a+tot+1); if(x>a[tot]) printf("%d ",n-a[tot]); else for(int i=1;i<=tot;i++) { if(a[i]>x) { printf("%d ",a[i]-a[i-1]-1); break; } } } } } return 0; }