题意 ：N个村子连成一条线，相邻的村子都有直接的地道进行相连，不相连的都由地道间接相连，三个命令，D x，表示x村庄被摧毁，R ，表示最后被摧毁的村庄已经重建了，Q x表示，与x直接或间接相连的村庄有多少个，当然包括他自己。
思路 ：这是一道用线段树，树状数组，还有STL都可以做的题。。。。因为用线段树的更新什么的太麻烦，。。。。。所以我用了树状数组
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std; const int maxn = ;
int tree[maxn],data[maxn] ;
bool vis[maxn] ;
int n , m ; int lowbit(int x)
{
return (x & (-x)) ;
} void add(int x,int value)
{
for(int i = x ; i <= n ; i += lowbit(i))
tree[i] += value ;
}
int get(int x)
{
int sum = ;
for(int i = x ; i ; i -= lowbit(i))
sum += tree[i] ;
return sum ;
} int binary_search(int v)
{
int l = , r = n+ ,i = n+;//n+2是为了防止最后一个村庄找不到的时候没有返回值
while(l <= r)
{
int mid = (l + r) >> ;
if(get(mid) >= v)
{
r = mid- ;
i = mid ;
}
else l = mid+ ;
}
return i ;
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
int a , i = ;
while(m--)
{
getchar() ;
char ch ;
scanf("%c",&ch) ;
if(ch == 'D')
{
scanf("%d",&a) ;
data[++i] = ++a ;//被摧毁的村庄都存在data数组里
vis[a] = true ;
add(a,) ;
}
else if(ch == 'Q')
{
scanf("%d",&a) ;
a ++ ;
if(vis[a]) printf("0\n") ;
else
{
int sum1,sum2 ;
a = get(a) ;
sum1 = binary_search(a) ;
sum2 = binary_search(a+) ;
printf("%d\n",sum2-sum1-) ;
}
}
else if(ch == 'R')
{
a = data[i--] ;
vis[a] = false ;
add(a,-) ;
}
}
}
return ;
}
以前用树状数组做的，现在用线段树做的，因为没有初始化WA到死，杭电上是多组数据，所以一开始也WA了，因为每次重建的时候建的是最后一个村子，将被摧毁的村子放入栈中就可以了，然后要标记一下，所有的村子存在即为0，摧毁了即为1，更新用单点，查询用区间，查询x村子时，寻找左边离他最近的那个被摧毁的村庄即1，以及最右边那个被摧毁的村庄，然后两个相减加1即为结果，但是如果他本身就被摧毁了直接是0。
//
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std ; int lz[*],p[ * ],vis[ * ],stk[*] ; void pushup(int rt)
{
p[rt] = p[rt << ] + p[rt << | ] ;
}
void update(int x,int l,int r,int rt,int sc)
{
if(l == r)
{
p[rt] = sc ;
return ;
}
int mid = (l+r) >> ;
if(x <= mid)
update(x,l,mid,rt << , sc) ;
else
update(x,mid+,r,rt << | , sc) ;
pushup(rt) ;
}
int query(int L,int R,int l,int r,int rt)
{
int sum = ;
if(L <= l && r <= R)
{
return p[rt] ;
}
int mid = (l+r) >> ;
if(mid >= L)
sum += query(L,R,l,mid,rt << ) ;
if(mid < R)
sum += query(L,R,mid+,r,rt << | ) ;
return sum ;
}
int findd(int l,int r,int x,int rt)
{
if(l == r)
{
return l;
}
int mid = (l+r) >> ;
if(x <= p[rt << ])
return findd(l,mid,x,rt << ) ;
else return findd(mid+,r,x-p[rt << ],rt << | ) ;
}
int main()
{
int n, m,x;
char ch[] ;
while(~scanf("%d %d",&n,&m))
{
int top = ;
memset(p,,sizeof(p)) ;
memset(vis,,sizeof(vis)) ;
for(int i = ; i < m ; i++)
{
scanf("%s",ch) ;
if(ch[] == 'R')
{
if(top != )
{
vis[stk[top-]] = ;//村庄存在即为0，被摧毁即为1
update(stk[top-],,n,,) ;
top-- ;
}
}
else if(ch[] == 'D')
{
scanf("%d",&x) ;
vis[x] = ;
stk[top++] = x ;
update(x,,n,,) ;
}
else if(ch[] == 'Q')
{
scanf("%d",&x) ;
if(vis[x])
{
printf("0\n") ;
continue ;
}
int l,r ;
int l1 = query(,x,,n,) ;//x村庄左边的和
if(l1 == )//如果和为0，说明x村庄左边全部都存在
l = ;
else l = findd(,n,l1,)+;//找出左边离x最近的那个一，既不存在的那个村庄
int r1 = query(x,n,,n,) ;
if(r1 == )
r = n;
else r = findd(,n,l1+,)- ;
printf("%d\n",r-l+) ;
}
}
}
return ;
}