学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1540

题意 ：

有N座相互连接的桥，每座桥都只和其前面和后面的两座桥连接，现在有三种操作：

D i :表示将第i座桥破坏；

Q i:表示询问与第i座桥相互连接的桥的数目；

R : 表示修好最近一座被毁坏的桥 ；

思路：

线段树。首先对于D操作和R操作，很简单，我们只需要用线段树的单点更新就可以了，R操作可以用一个栈维护。比较麻烦的就是Q操作了，对于每次的Q操作，我们可以先求出i点左边的与之相连的点的个数，再求出其右边与之相连的点的个数，最后相加就可以了。而求其右边与之相连的点的个数的时候可以用一颗线段树来求， 线段树的每个节点记录三个信息：col表示该区间的颜色，-1：混合，0：毁坏，1 ：完好 ； lnum ：表示该区间左边与左端点相连的点的个数； rnum表示相应的右端点。
这样当我们每次询问的时候，对于一个区间(a,b)如果 b<=mid 那么就询问左孩子，如果 mid<a ，就去询问右孩子，如果两边都有的话，就先求出左孩子的(a , mid)中以a为端点的相连的长度，如果该长度等于mid-a+1，那么就要加上右孩子的左边的相连的长度。否则就只有（a,mid ）中的长度了。

代码：

#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
#define LL(a) ( (a)<<1 )
#define RR(a) ( (a)<<1|1 )
const int MAXN = 50010 ;

int col[MAXN<<2] ;
int lnum[MAXN<<2] , rnum[MAXN<<2] ;
int N , M ;
stack<int>  s;

void build(int l ,int r, int idx){
    col[idx] = 1 ;
    lnum[idx] = rnum[idx] = r-l+1 ;
    if( l == r )    return ;
    int mid = (l + r) >> 1  ;
    build( l , mid , LL(idx) ) ;
    build( mid+1 , r , RR(idx) ) ;
}

void up(int l ,int r, int idx){
    int mid = (l + r) >> 1 ;
    if( col[ LL(idx) ] == col[ RR(idx) ] )
        col[idx] = col[ LL(idx) ] ;
    else
        col[idx] = -1 ;
    lnum[idx] = lnum[ LL(idx) ] ;
    if( lnum[ LL(idx) ] == mid-l+1 )
        lnum[idx] += lnum[ RR(idx) ] ;
    rnum[idx] = rnum[ RR(idx) ] ;
    if( rnum[ RR(idx) ] == r - mid )
        rnum[idx] += rnum[ LL(idx) ] ;
}

void update(int l ,int r, int idx , int pos , int vv ){
    if( l == r ){
        col[idx] = vv ;
        if( vv == 0 ){
            lnum[idx] = rnum[idx] = 0 ;
        }
        else
            lnum[idx] = rnum[idx]  =1 ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    if( pos <= mid )    update(l , mid , LL(idx) , pos , vv) ;
    else                update(mid+1 , r , RR(idx) , pos ,vv ) ;
    up(l, r ,idx);
}

int query(int l ,int r, int idx, int a , int b ){
    if(l==a && r==b){
        return lnum[idx] ;
    }
    int mid = (l + r) >> 1 ;
    if( b<=mid )    return query(l , mid , LL(idx) , a , b );
    else if( mid<a )    return query(mid+1 , r ,RR(idx) , a, b);
    else{
        int a1 = query(l , mid , LL(idx) , a, mid );
        int a2 = query(mid+1 , r , RR(idx) , mid+1 , b );
        if(a1 == mid-a+1){
            a1 += a2 ;
        }
        return a1 ;
    }
}

int query2(int l ,int r, int idx, int a, int b){
    if(a==l && b==r){
        return rnum[idx] ;
    }
    int mid = (l + r) >> 1 ;
    if( b<=mid )    return query2(l, mid , LL(idx) , a , b );
    else if( mid<a )    return query2(mid+1 , r, RR(idx) , a , b);
    else{
        int a1 = query2( l , mid , LL(idx) , a,  mid );
        int a2 = query2( mid+1 , r, RR(idx) , mid+1, b );
        if( a2 == b - mid )
            a2 += a1 ;
        return a2 ;
    }
}

int main(){
    char op[10] ;
    int a ;
    while( scanf("%d %d",&N,&M) == 2){
        build(1 , N ,1 );
        while( !s.empty() ) s.pop() ;
        for(int i=1;i<=M;i++){
            scanf("%s",op);
            if( op[0] == 'D' ){
                scanf("%d",&a);
                update(1 , N , 1 , a , 0 );
                s.push( a );
            }
            else if( op[0] == 'Q' ){
                scanf("%d",&a);
                int a1 = query(1 , N ,1 ,a , N );
                if(a-1>=1 && a1>0){
                    int a2 = query2(1 , N ,1 ,1 , a-1 );
                    a1 += a2 ;
                }
                printf("%d\n",a1);
            }
            else{
                a = s.top() ; s.pop() ;
                update(1 , N ,1 ,a , 1 );
            }
        }
    }
    return 0 ;
}