HDU 3397 Sequence operation 线段树

Sequence operation

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5626    Accepted Submission(s): 1669

Problem Description

lxhgww got a sequence contains n characters which are all '0's or '1's.
We have five operations here:
Change operations:
0 a b change all characters into '0's in [a , b]
1 a b change all characters into '1's in [a , b]
2 a b change all '0's into '1's and change all '1's into '0's in [a, b]
Output operations:
3 a b output the number of '1's in [a, b]
4 a b output the length of the longest continuous '1' string in [a , b]

 

Input

T(T<=10) in the first line is the case number.
Each case has two integers in the first line: n and m (1 <= n , m <= 100000).
The next line contains n characters, '0' or '1' separated by spaces.
Then m lines are the operations:
op a b: 0 <= op <= 4 , 0 <= a <= b < n.

 

Output

For each output operation , output the result.

 

Sample Input

1 10 10 0 0 0 1 1 0 1 0 1 1 1 0 2 3 0 5 2 2 2 4 0 4 0 3 6 2 3 7 4 2 8 1 0 5 0 5 6 3 3 9

 

Sample Output

5 2 6 5

 

Author

lxhgww&&shǎ崽

 

Source

HDOJ Monthly Contest – 2010.05.01

传送门：HDU 3397 Sequence operation
题目大意：给你长度为n的一串01序列，m次操作。（n,m <= 100000）
一共五种操作：
0 L R 将【L，R】区间内的数覆盖为 0 。
1 L R 将【L，R】区间内的数覆盖为 1 。
2 L R 将【L，R】区间内的数异或（ 0 变成 1，1 变成 0） 。
3 L R 输出【L，R】区间内的 1 的个数。
4 L R 输出【L，R】区间内最长的连续 1 的长度。

题目分析：
区间合并问题。
因为有两个覆盖操作以及一个异或操作，所以需要set标记（覆盖）以及cha标记（异或）（不要在意名字）。
因为本题的01异或，0和1的信息会进行交换，所以我们需要特别的分别记录每个区间的0和1的左连续最大lmax，区间最大mmax，右连续最大rmax。
对于覆盖操作的执行，同时将异或操作清零，因为无论之前怎么异或或覆盖，都会被新的操作覆盖。
对于异或操作的执行，尤其要注意，如果一个区间同时存在异或操作及覆盖操作，一定是覆盖操作后到（为什么？根据覆盖操作的执行思考一下）。对异或操作异或就行了。因为在PushDown里面先执行的是set，所以这样是不会影响结果的。
然后注意一下细节就行了。

代码如下：

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

#define lson l , m , o << 1
#define rson m + 1 , r , o << 1 | 1
#define rt l , r , o

const int maxN = 500000 ;

int lmax[2][maxN] , mmax[2][maxN] , rmax[2][maxN] , nnum[2][maxN];
int set[maxN] , cha[maxN] ;

int max ( const int X , const int Y ) {
    if ( X > Y ) return X ;
    return Y ;
}

int min ( const int X , const int Y ) {
    if ( X < Y ) return X ;
    return Y ;
}

void swap ( int &X , int &Y ) {
    int tmp = X ; X = Y ; Y = tmp ;
}

void PushUp ( int x , int l , int r , int o ) {
    int m = ( l + r ) >> 1 ;
    lmax[x][o] = lmax[x][o << 1] ;
    rmax[x][o] = rmax[x][o << 1 | 1] ;
    mmax[x][o] = max ( mmax[x][o << 1] , mmax[x][o << 1 | 1] ) ;
    nnum[x][o] = nnum[x][o << 1] + nnum[x][o << 1 | 1] ;
    if ( rmax[x][o << 1] && lmax[x][o << 1 | 1] ) {
        mmax[x][o] = max ( mmax[x][o] , rmax[x][o << 1] + lmax[x][o << 1 | 1] ) ;
        if ( lmax[x][o << 1] == m - l + 1 ) {
            lmax[x][o] += lmax[x][o << 1 | 1] ;
        }
        if ( rmax[x][o << 1 | 1] == r - m ) {
            rmax[x][o] += rmax[x][o << 1] ;
        }
    }
}

void init ( int x , int o , int len ) {
    set[o] = x ;
    cha[o] = 0 ;
    nnum[x][o] = lmax[x][o] = mmax[x][o] = rmax[x][o] = len ;
    nnum[x ^ 1][o] = lmax[x ^ 1][o] = mmax[x ^ 1][o] = rmax[x ^ 1][o] = 0 ;
}

void change ( int o ) {
    cha[o] ^= 1 ;
    swap ( lmax[0][o] , lmax[1][o] ) ;
    swap ( mmax[0][o] , mmax[1][o] ) ;
    swap ( rmax[0][o] , rmax[1][o] ) ;
    swap ( nnum[0][o] , nnum[1][o] ) ;
}

void PushDown ( int l , int r , int o ) {
    if ( ~set[o] ) {
        int m = ( l + r ) >> 1 ;
        init ( set[o] , o << 1 , m - l + 1 ) ;
        init ( set[o] , o << 1 | 1 , r - m ) ;
        set[o] = -1 ;
    }
    if ( cha[o] ) {
        change ( o << 1 ) ;
        change ( o << 1 | 1 ) ;
        cha[o] = 0 ;
    }
}

void Build ( int l , int r , int o ) {
    set[o] = -1 ;
    cha[o] = 0 ;
    if ( l == r ) {
        int x ;
        scanf ( "%d" , &x ) ;
        init ( x , o , 1 ) ;
        return ;
    }
    int m = ( l + r ) >> 1 ;
    Build ( lson ) ;
    Build ( rson ) ;
    PushUp ( 0 , rt ) ;
    PushUp ( 1 , rt ) ;
}

void Update ( int L , int R , int x , int l , int r , int o ) {
    if ( L <= l && r <= R ) {
        if ( 2 == x ) change ( o ) ;
        else init ( x , o , r - l + 1 ) ;
        return ;
    }
    PushDown ( rt ) ;
    int m = ( l + r ) >> 1 ;
    if ( L <= m ) Update ( L , R , x , lson ) ;
    if ( m <  R ) Update ( L , R , x , rson ) ;
    PushUp ( 0 , rt ) ;
    PushUp ( 1 , rt ) ;
}

int Query ( int L , int R , int x , int l , int r , int o ) {
    if ( L <= l && r <= R ) {
        if ( 3 == x ) return nnum[1][o] ;
        if ( 4 == x ) return mmax[1][o] ;
    }
    PushDown ( rt ) ;
    int m = ( l + r ) >> 1 ;
    if ( 3 == x ) {
        int ans = 0 ;
        if ( L <= m ) ans += Query ( L , R , x , lson ) ;
        if ( m <  R ) ans += Query ( L , R , x , rson ) ;
        return ans ;
    }
    if ( 4 == x ) {
        int tmp1 = 0 , tmp2 = 0 , tmp3 = 0 ;
        if ( L <= m ) tmp1 = Query ( L , R , x , lson ) ;
        if ( m <  R ) tmp2 = Query ( L , R , x , rson ) ;
        if ( L <= m && m < R && rmax[1][o << 1] && lmax[1][o << 1 | 1] ) {
            tmp3 = min ( m - L + 1 , rmax[1][o << 1] ) + min ( R - m , lmax[1][o << 1 | 1] ) ;
        }
        return max ( max ( tmp1 , tmp2 ) , tmp3 ) ;
    }
}

void work () {
    int n , m , l , r , x ;
    scanf ( "%d%d" , &n , &m ) ;
    Build ( 1 , n , 1 ) ;
    while ( m -- ) {
        scanf ( "%d%d%d" , &x , &l , &r ) ;
        if ( 2 >= x ) Update ( l + 1 , r + 1 , x , 1 , n , 1 ) ;
        else printf ( "%d\n" , Query ( l + 1 , r + 1 , x , 1 , n , 1 ) ) ;
    }
}

int main () {
    int T ;
    scanf ( "%d" , &T ) ;
    while ( T -- ) work () ;
    return 0 ;
}