[PKU/POJ][2892][Tunnel Warfare][线段树]

题目意思为有一系列村庄，然后对一些村庄进行破坏或修复。让你求与某村庄直接或间接相连且都没有破坏的村庄数量。

 

对于每一个区间，用线段树维护从区间左端点开始的最大连续没破坏的村庄数量 Lx 以及以区间右端点结点的最大连续没破坏的村庄数 Rx，很容易更新这两个值及求出要求的数量。

 

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int n, m;
int const N= 50010;

struct Node{
    int Lx, Rx;
    int value;
}tb[N<<2];

int stack[N], top= 0;

void build( int L, int R, int rt ){
    if( L== R ){
        tb[rt].value= 0;
        tb[rt].Lx= tb[rt].Rx=1;
        return; }
    
    int mid= (L+ R)>>1;
    build( L, mid, rt<<1 );
    build( mid+ 1, R, rt<<1|1 );
    
    tb[rt].Lx= tb[rt].Rx= R- L+ 1;
}

void update( int x, int y, int L, int R, int rt ){
    if( L== R ){
        tb[rt].value= y;
        if( y ) tb[rt].Lx= tb[rt].Rx= 0;
        else    tb[rt].Lx= tb[rt].Rx= 1;
        return;
    }
    
    int mid= (L+ R)>>1;
    if( x<= mid ) update( x, y, L, mid, rt<<1 );
    else update( x, y, mid+ 1, R, rt<<1|1 );
    
    if( tb[rt<<1].Lx== mid- L+ 1 ) tb[rt].Lx= tb[rt<<1].Lx+ tb[rt<<1|1].Lx;
    else tb[rt].Lx= tb[rt<<1].Lx;
    
    if( tb[rt<<1|1].Rx== R- mid ) tb[rt].Rx= tb[rt<<1|1].Rx+ tb[rt<<1].Rx;
    else tb[rt].Rx= tb[rt<<1|1].Rx;
}

int query( int x, int L, int R, int rt ){
    if( L== R ) return tb[rt].value== 0;
    
    int mid= (L+ R)>>1;
    if( x<= mid ) {
        if( x> mid- tb[rt<<1].Rx ) return tb[rt<<1].Rx+ tb[rt<<1|1].Lx;
        else return query( x, L, mid, rt<<1 );
    }
    else{
        if( x<= mid+ tb[rt<<1|1].Lx ) return tb[rt<<1].Rx+ tb[rt<<1|1].Lx;
        return query( x, mid+ 1, R, rt<<1|1 );
    }
}


int main(){
    while( scanf("%d%d",&n,&m )!= EOF ){
        build( 1, n, 1 ); top= 0;
        for( int i= 0; i< m; ++i ){
            char str[5];
            int d;
            scanf("%s",str );
            
            if( str[0]== 'D' ){
                scanf("%d",&d );
                
                update( d, 1, 1, n, 1 );
                stack[++top]= d;
            }
            else if( str[0]== 'Q' ){
                scanf("%d",&d );
                
                printf("%d\n", query( d, 1, n, 1 ) );
            }
            else{
                if( top== 0 ) continue;
                update( stack[top--], 0, 1, n, 1 );
            }
        }
    }
    
    return 0;
}