首页 > 代码库 > Hdu 3397 Sequence operation(线段树多操作，Lazy思想，成段更新)

Hdu 3397 Sequence operation(线段树多操作，Lazy思想，成段更新)

2024-08-04 06:15:22   219人阅读

Sequence operation

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


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
 

Recommend
lcy   |   We have carefully selected several similar problems for you:  1828 1542 1540 2871 1255 
 

题目大意： 
0 a b将区间[a,b]所有数全部变成0 
1 a b将区间[a,b]所有数全部变成1 
2 a b将区间[a,b]中所有数0 1互换，0变1,1变0 
3 a b输出区间[a,b]中1的个数 
4 a b输出区间[a,b]中最长连续1的个数 


题解：

分别记录节点左右中最长连续1和0，op标记区间更新为1或0，xo则标记异或。

CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<map>

#define N 100010
#define Mod 10000007
#define lson l,mid,idx<<1
#define rson mid+1,r,idx<<1|1
#define lroot idx<<1
#define rroot idx<<1|1

typedef long long ll;

const int INF = 1000010;

using namespace std;

struct node
{
    int lmax, rmax, mmax;///左右中最长连续1
    int lm, rm, mm;///左右中最长连续0
    int sum;///1的和
    int op;///0:标记区间更新为0,1则为1，-1不操作
    int xo;
} tree[N << 2];

int a[N];

void pushup ( int idx, int m )
{
    tree[idx].sum = tree[lroot].sum + tree[rroot].sum;
    ///lmax,lm
    tree[idx].lmax = tree[lroot].lmax;
    tree[idx].lm = tree[lroot].lm;
    if ( tree[lroot].lmax == ( m - m / 2 ) )
        tree[idx].lmax += tree[rroot].lmax;
    else if ( tree[lroot].lm == ( m - m / 2 ) )
        tree[idx].lm += tree[rroot].lm;
    ///rm,rmax
    tree[idx].rmax = tree[rroot].rmax;
    tree[idx].rm = tree[rroot].rm;
    if ( tree[rroot].rmax == m / 2 )
        tree[idx].rmax += tree[lroot].rmax;
    else if ( tree[rroot].rm == m / 2 )
        tree[idx].rm += tree[lroot].rm;
    ///mm,mmax
    tree[idx].mmax = max ( tree[lroot].mmax, tree[rroot].mmax );
    tree[idx].mm = max ( tree[lroot].mm, tree[rroot].mm );
    tree[idx].mmax = max ( tree[idx].mmax, tree[rroot].lmax + tree[lroot].rmax );
    tree[idx].mm = max ( tree[idx].mm, tree[rroot].lm + tree[lroot].rm );
}

void pushdown ( int idx, int m )///m为区间长度
{
    if ( m == 1 )
        return;
    if ( tree[idx].op == 1 )///成段更新为1
    {
        tree[lroot].op = tree[rroot].op = tree[idx].op;
        tree[lroot].sum = tree[lroot].lmax = tree[lroot].rmax = tree[lroot].mmax = m - m / 2;
        tree[rroot].sum = tree[rroot].lmax = tree[rroot].rmax = tree[rroot].mmax = m / 2;
        tree[rroot].lm = tree[rroot].rm = tree[lroot].lm = tree[lroot].rm = tree[lroot].mm = tree[rroot].mm = 0;
        tree[idx].op = -1;
        tree[rroot].xo = tree[lroot].xo = 0;
    }
    else if ( tree[idx].op == 0 )///成段更新为0
    {
        tree[lroot].op = tree[rroot].op = tree[idx].op;
        tree[lroot].sum = tree[lroot].lmax = tree[lroot].rmax = 0;
        tree[rroot].sum = tree[rroot].lmax = tree[rroot].rmax = 0;
        tree[lroot].mmax = tree[rroot].mmax = 0;
        tree[rroot].lm = tree[rroot].rm = tree[rroot].mm = m / 2;
        tree[lroot].lm = tree[lroot].rm = tree[lroot].mm = m - m / 2;
        tree[idx].op = -1;
        tree[rroot].xo = tree[lroot].xo = 0;
    }
    if ( tree[idx].xo )///1变0,0变1
    {
        tree[lroot].xo ^= 1;
        tree[rroot].xo ^= 1;
        tree[lroot].sum = m - m / 2 - tree[lroot].sum;
        tree[rroot].sum = m / 2 - tree[rroot].sum;
        swap ( tree[lroot].lmax, tree[lroot].lm );
        swap ( tree[rroot].lmax, tree[rroot].lm );
        swap ( tree[lroot].rmax, tree[lroot].rm );
        swap ( tree[rroot].rmax, tree[rroot].rm );
        swap ( tree[lroot].mmax, tree[lroot].mm );
        swap ( tree[rroot].mmax, tree[rroot].mm );
        tree[idx].xo = 0;
    }
}

void  build ( int l, int r, int idx )
{
    tree[idx].xo = 0;
    tree[idx].op = -1;
    if ( l == r )
    {
        tree[idx].sum = a[l];
        tree[idx].mmax = tree[idx].lmax = tree[idx].rmax = a[l];
        tree[idx].mm = tree[idx].rm = tree[idx].lm = a[l] ^ 1;
        return;
    }
    int mid = ( l + r ) >> 1;
    build ( lson );
    build ( rson );
    pushup ( idx, r - l + 1 );
}

void update_1 ( int l, int r, int idx, int begin, int end, int k ) ///更新0->1,1->0成段
{
    pushdown ( idx, r - l + 1 );
    if ( begin <= l && end >= r )
    {
        tree[idx].op = k;
        tree[idx].xo = 0;
        if ( k )
        {
            tree[idx].sum = r - l + 1;
            tree[idx].lmax = tree[idx].rmax = tree[idx].mmax = r - l + 1;
            tree[idx].rm = tree[idx].lm = tree[idx].mm = 0;
        }
        else
        {
            tree[idx].sum = 0;
            tree[idx].lmax = tree[idx].rmax = tree[idx].mmax = 0;
            tree[idx].rm = tree[idx].lm = tree[idx].mm = r - l + 1;
        }
        return;
    }
    int mid = ( l + r ) >> 1;
    if ( begin <= mid )
        update_1 ( lson, begin, end, k );
    if ( end > mid )
        update_1 ( rson, begin, end, k );
    pushup ( idx, r - l + 1 );
}

void update_2 ( int l, int r, int idx, int begin, int end ) ///yihuo
{
    pushdown ( idx, r - l + 1 );
    if ( l >= begin && r <= end )
    {
        tree[idx].xo = 1;
        tree[idx].sum = r - l + 1 - tree[idx].sum;
        swap ( tree[idx].lmax, tree[idx].lm );
        swap ( tree[idx].rmax, tree[idx].rm );
        swap ( tree[idx].mm, tree[idx].mmax );
        return;
    }
    int mid = ( l + r ) >> 1;
    if ( begin <= mid )
        update_2 ( lson, begin, end );
    if ( end > mid )
        update_2 ( rson, begin, end );
    pushup ( idx, r - l + 1 );
}

int query_1 ( int l, int r, int idx, int begin, int end ) ///查询1的个数
{
    pushdown ( idx, r - l + 1 );
    if ( begin <= l && end >= r )
        return tree[idx].sum;
    int mid = ( l + r ) >> 1;
    int ans = 0;
    if ( begin <= mid )
        ans += query_1 ( lson, begin, end );
    if ( end > mid )
        ans += query_1 ( rson, begin, end );
    return ans;
}

int query_2 ( int l, int r, int idx, int begin, int end ) ///查询连续的1的最大长度
{
    pushdown ( idx, r - l + 1 );
    if ( begin <= l && end >= r )
        return tree[idx].mmax;
    int mid = ( l + r ) >> 1;
    int len = 0;
    if ( end > mid )
        len = max ( len, query_2 ( rson, begin, end ) );
    if ( begin <= mid )
        len = max ( len, query_2 ( lson, begin, end ) );
    len = max ( len, min ( mid - begin + 1, tree[lroot].rmax ) + min ( end - mid, tree[rroot].lmax ) );
    return len;
}

int main()
{
    //freopen ( "in.txt", "r", stdin );
    int t;
    while ( cin >> t )
    {
        while ( t-- )
        {
            int n, m;
            scanf ( "%d%d", &n, &m );
            for ( int i = 1; i <= n; i++ )
                scanf ( "%d", &a[i] );
            build ( 1, n, 1 );
            int begin, end, x;
            while ( m-- )
            {
                scanf ( "%d%d%d", &x, &begin, &end );
                begin++, end++;
                switch ( x )
                {
                case 2:
                    update_2 ( 1, n, 1, begin, end );
                    break;
                case 3:
                    printf ( "%d\n", query_1 ( 1, n, 1, begin, end ) );
                    break;
                case 4:
                    printf ( "%d\n", query_2 ( 1, n, 1, begin, end ) );
                    break;
                default:
                    update_1 ( 1, n, 1, begin, end, x );
                }
            }
        }
    }
    return 0;
}


Hdu 3397 Sequence operation(线段树多操作，Lazy思想，成段更新)


联系
我们