可能是他们理解错题目了，这里每个poster是占一个点的，不是占一个线段，所以答案应该是2、2、4，附上我的代码，注意我的线段树的叶子节点是left == right，是一个点而不是一个元线段！


#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
struct Segment{
    int l, r;
};
//完全二叉树 
int segTree[70000];
Segment seg[10001];
int pt[20002];
int len;
int n;
bool flag[20010];

void insert( int idx, int left, int right, int a, int b, int  color ){
    if( segTree[idx] != color ){
        if( left == a && right == b ){
            segTree[idx] = color;
        }else{
            int mid = ( left + right ) >> 1;
            if( segTree[idx] >= 0 ){
                segTree[ idx<<1 ] = segTree[idx];
                segTree[(idx<<1)+1] = segTree[idx];
                segTree[idx] = -1;
            }
            
            if( b <= mid ){
                insert( idx << 1, left, mid, a, b, color );
            }else if( a > mid ){
                insert( ( idx << 1 ) + 1, mid+1, right, a, b, color );
            }else{
                insert( idx << 1, left, mid, a, mid, color );
                insert( ( idx << 1 ) + 1, mid+1, right, mid+1, b, color );
            }
        }
    }
}

void scount( int idx, int left, int right ){
    if( segTree[idx] >= 0 ){
        flag[segTree[idx]] = true;
    }else{
        if( right != left  ){ //not leaf node
            int mid = ( left + right ) >> 1;
            scount( idx << 1, left, mid );
            scount( ( idx << 1 ) + 1, mid+1, right );
        }
    }
}

int main(){
    int T;
    bitset<10000001> bs;
    scanf( "%d", &T );
    while(T--){
        scanf( "%d", &n );
        memset( segTree, 0, sizeof( segTree ) );
        len = 0;
        for( int i=0; i<n; ++i ){
            scanf( "%d%d", &seg[i].l, &seg[i].r );
            if( !bs.test( seg[i].l ) ){
                pt[len++] = seg[i].l;
                bs.set( seg[i].l );
            }
            
            if( !bs.test( seg[i].r  ) ){
                pt[len++] = seg[i].r ;
                bs.set( seg[i].r  );
            }
        }
        
        sort( pt, pt+len );
        for( int i=0; i<len; ++i ){ // clear
            bs.reset( pt[i] );
        }
        int nl,nr;
        for( int i=0; i<n; ++i ){
            nl = lower_bound( pt, pt+len, seg[i].l ) - pt;
            nr = lower_bound( pt, pt+len, seg[i].r ) - pt;
            insert( 1, 0, len-1, nl, nr, i+1 );
        }
        
        memset( flag, 0, len+1 );
        scount( 1, 0, len-1 );
        int res = 0;
        for( int i=1; i<=len; ++i ){
            if( flag[i] )
                ++res;
        }
        printf( "%d\n", res );
        
    }
    return 0;
}

• Re:《相信很多人都过不了这组数据吧》的答案应该是2、2、4 (8) 201293123 2013-08-18 00:40:02
  • Re:《相信很多人都过不了这组数据吧》的答案应该是2、3、4 (12) 201293123 2013-08-18 00:40:13