题目描述

描述 县城里有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条。

输出格式

对于每一个被围堵的士兵,输出该士兵能够到达的房子数。

样例

输入样例

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

输出样例

1
0
2
4

Code

这道题可以用线段树来做。找到x前面的第一个被摧毁的点,然后找到x后面第一个被摧毁的点,再相减即可。即单点修改,单点查询,只是要将线段树模板改动一下。

#include<bits/stdc++.h>
using namespace std;

const int maxn=200010,inf=1e9;
int sum[maxn],stac[maxn],top;
int m,n,bc,fr;

int __read(){
	int Value=0,Base=1;char Ch=getchar();
	for(;!isdigit(Ch);Ch=getchar())if(Ch=='-')Base=-1;
	for(;isdigit(Ch);Ch=getchar())Value=Value*10+(Ch^'0');
	return Value*Base;
}

void Build(int rt,int l,int r){
	if(l==r){
		if(l==0 && r==n+1)
		sum[rt]=1;
		return ;
	}
	int mid=(l+r)>>1;
	Build(rt<<1,l,mid);
	Build(rt<<1|1,mid+1,r);
}

void Update(int rt,int l,int r,int L,int R,int fl){
	int mid=(l+r)>>1;
	if(L==l && R==r){
		sum[rt]=fl;
		return ;
	}
	if(L<=mid)Update(rt<<1,l,mid,L,R,fl);
	if(R>mid)Update(rt<<1|1,mid+1,r,L,R,fl);
	sum[rt]=sum[rt<<1]|sum[rt<<1|1];
}

int Query_fr(int rt,int l,int r){
	int mid=(l+r)>>1;
	if(l==r)
		if(sum[rt])return l;
		else return 0;
	if(sum[rt<<1|1])return Query_fr(rt<<1|1,mid+1,r);
	else if(sum[rt<<1])return Query_fr(rt<<1,l,mid);
	else return -inf;
}

int Query_bc(int rt,int l,int r){
	int mid=(l+r)>>1;
	if(l==r)
		if(sum[rt])return l;
		else return 1e9;
	if(sum[rt<<1])return Query_bc(rt<<1,l,mid);
	else if(sum[rt<<1|1])return Query_bc(rt<<1|1,mid+1,r);
	else return inf;
}

void Query(int rt,int l,int r,int L,int R,int fl){
	int mid=(l+r)>>1;
	if(L<=l && r<=R){
		if(fl==1)fr=max(fr,Query_fr(rt,l,r));
		else bc=min(bc,Query_bc(rt,l,r));
		return ;
	}
	if(L<=mid)Query(rt<<1,l,mid,L,R,fl);
	if(R>mid)Query(rt<<1|1,mid+1,r,L,R,fl);
}

int Getc(){-
	char Ch=getchar();
	for(;!isgraph(Ch);Ch=getchar());
	return Ch;
}

int main( ){
    int m,n,j,k,i,las;
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
    scanf("%d%d",&n,&m);
	Build(1,0,n+1);
	for(i=1;i<=m;i++){
		char Ch=Getc();
		if(Ch=='D'){
			int x=(stac[++top]=__read());
			Update(1,0,n+1,x,x,1);
		}
		if(Ch=='Q'){
			int x=__read();fr=0;bc=n+1;
			Query(1,0,n+1,0,x,1);
			Query(1,0,n+1,x,n+1,2);
			printf("%d\n",max(bc-fr-1,0));
		}
		if(Ch=='R'){
			int x=stac[top--];
			Update(1,0,n+1,x,x,0);
		}
	}
    return 0;
}