BZOJ-3526: [Poi2014]Card(线段树)

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3526

假如不带修改，可以直接扫一遍解决，但是这个不好动态维护，我们发现分治同样可以解决这个问题，相当维护一下左边两个数到右边两个数是否可行，然后这样可以方便的线段树了，但是这样还是有点慢，考虑到左边的数固定的话，右边对应的数要越小越好，那么对于一个区间[l,r]维护一下l两个数对应的右边的数的最小值即可，如果不可行就正无穷表示，线段树上直接修改。。。没了

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

const int inf = 0x7fffffff ;

const int maxn = 201000 ;

 

int a[ maxn ][ 2 ] ;

 

struct node {

        node *lc , *rc ;

        int l , r , mid , c[ 2 ] ;

        inline void update(  ) {

                c[ 0 ] = c[ 1 ] = inf ;

                if ( lc -> c[ 0 ] <= a[ mid + 1 ][ 0 ] ) c[ 0 ] = min( c[ 0 ] , rc -> c[ 0 ] ) ;

                if ( lc -> c[ 0 ] <= a[ mid + 1 ][ 1 ] ) c[ 0 ] = min( c[ 0 ] , rc -> c[ 1 ] ) ;

                if ( lc -> c[ 1 ] <= a[ mid + 1 ][ 0 ] ) c[ 1 ] = min( c[ 1 ] , rc -> c[ 0 ] ) ;

                if ( lc -> c[ 1 ] <= a[ mid + 1 ][ 1 ] ) c[ 1 ] = min( c[ 1 ] , rc -> c[ 1 ] ) ;

        }

} sgt[ maxn << 1 ] ;

 

node *pt = sgt , *root ;

 

void build( int l , int r , node* &t ) {

        t = pt ++ ;

        t -> l = l , t -> r = r ;

        if ( l == r ) {

                t -> c[ 0 ] = a[ l ][ 0 ] , t -> c[ 1 ] = a[ l ][ 1 ] ; return ;

        }

        t -> mid = ( l + r ) >> 1 ;

        build( l , t -> mid , t -> lc ) , build( t -> mid + 1 , r , t -> rc ) ;

        t -> update(  ) ;

}

 

void change( int x , node *t ) {

        if ( t -> l == t -> r ) {

                t -> c[ 0 ] = a[ t -> l ][ 0 ] , t -> c[ 1 ] = a[ t -> l ][ 1 ] ; return ;

        }

        change( x , x <= t -> mid ? t -> lc : t -> rc ) ;

        t -> update(  ) ;

}

 

int ch ;

 

inline void getint( int &t ) {

        for ( ch = getchar(  ) ; ch < '0' || ch > '9' ; ch = getchar(  ) ) ; t = ch - '0' ;

        for ( ch = getchar(  ) ; ch >= '0' && ch <= '9' ; ch = getchar(  ) ) t = t * 10 + ch - '0' ;

}

 

int n , m ;

 

int main(  ) {

        getint( n ) ;

        for ( int i = 0 ; i ++ < n ; ) getint( a[ i ][ 0 ] ) , getint( a[ i ][ 1 ] ) ;

        build( 1 , n , root ) ;

        getint( m ) ;

        while ( m -- ) {

                int x , y ; getint( x ) , getint( y ) ;

                swap( a[ x ][ 0 ] , a[ y ][ 0 ] ) , swap( a[ x ][ 1 ] , a[ y ][ 1 ] ) ;

                change( x , root ) , change( y , root ) ;

                printf( min( root -> c[ 0 ] , root -> c[ 1 ] ) < inf ? "TAK\n" : "NIE\n" ) ;

        }

        return 0 ;

}