线段树求调,orz

P1253 扶苏的问题

A_chicken_boy @ 2024-04-25 18:41:16

#include<bits/stdc++.h>
using namespace std ;
#define N 1000005
#define _f(i,a,b) for ( int i = (a) ; i <= (b) ; ++i )
inline int _c ( ){
    int XX=0,FF=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            FF*=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        XX=XX*10+ch-48;
        ch=getchar();
    }
    return XX*FF;
}
int n , qs ;
int a[N] ;
struct S{
    int l , r ;
    int flag1 , flag2 , flag3 ;
    int maxx ;
}t[4*N];
void Up ( int q ){
    t[q].maxx = max ( t[q<<1].maxx , t[q<<1|1].maxx ) ;
}
void Down ( int q ){
    if ( t[q].flag3 ){
        t[q<<1].flag1 = t[q].flag1 ;
        t[q<<1|1].flag1 = t[q].flag1 ;
        t[q<<1].flag2 = t[q].flag2 ;
        t[q<<1|1].flag2 = t[q].flag2 ;
        t[q<<1].maxx = t[q].flag1 + t[q].flag2 ;
        t[q<<1|1].maxx = t[q].flag2 + t[q].flag1 ;
        t[q<<1].flag3 = t[q<<1|1].flag3 = 1 ;
    }else{
        t[q<<1].flag2 += t[q].flag2 ;
        t[q<<1|1].flag2 += t[q].flag2 ;
        t[q<<1].maxx += t[q].flag2 ;
        t[q<<1|1].maxx += t[q].flag2  ;
    }
    t[q].flag1 = t[q].flag2 = t[q].flag3 = 0 ;
}
void build (int q , int l , int r ){
    t[q].l = l ;
    t[q].r = r ;
    t[q].flag3 = 0 ;
    t[q].maxx = -1e8 ;
    if ( l == r ){
        t[q].maxx = a[l] ;
        return ;
    }
    int mid = ( l + r ) >> 1 ;
    build ( q <<1 , l , mid );
    build ( q<<1|1 , mid + 1 , r ) ;
    Up(q) ;
}
void change ( int q , int l , int r , int x ){
//  cout <<t[q].l << " " << t[q].r << endl ;
    if ( l <= t[q].l && t[q].r <= r ){
        t[q].flag1 += x ;
        t[q].flag2 = 0 ;
        t[q].maxx = x ;
        t[q].flag3 = 1 ;
        return ;
    }
    Down ( q ) ;
    int mid = ( t[q].l + t[q].r ) >> 1 ;
    if ( l <= mid ) change ( q << 1 , l , r , x ) ;
    if ( r > mid ) change ( q << 1 | 1 , l , r , x ) ;
    Up ( q ) ;
}
void add ( int q , int l , int r , int x ){
    if( l <= t[q].l && t[q].r <= r ){
        t[q].flag2 += x ;
        t[q].maxx += x ;
        return ;
    }
    Down ( q ) ;
    int mid = ( t[q].l + t[q].r ) >> 1 ;
    if ( l <= mid ) change ( q << 1 , l , r , x ) ;
    if ( r > mid ) change ( q << 1 | 1 , l , r , x ) ;
    Up (q ) ;
}
long long askk ( int q , int l , int r ){
    if ( l <= t[q].l && t[q].r <= r ){
        return t[q].maxx ;
    }
    Down ( q ) ;
    long long maxn = -1e18 ;
    int mid = ( t[q].l + t[q].r ) >> 1 ; 
    if ( l <= mid ) maxn = max ( maxn , askk ( q<< 1 , l , r ) ) ;
    if ( r > mid ) maxn = max ( maxn , askk ( q << 1 | 1 , l , r  ) ) ;
    return maxn ;
}
int main ( ){
    cin >> n >> qs ;
    _f( i , 1 , n ){
        a[i] = _c( ) ;
    }
    build ( 1 , 1 , n ) ;
    int op ;
    int l , r , x ;
    _f ( i , 1 , qs ){
        op = _c( ) ;
        if ( op == 1 ){
            l = _c( );
            r = _c( );
            x = _c( );

            change ( 1 , l , r , x ) ;
        }else if ( op == 2 ){
            l = _c( ) , r = _c( ) , x = _c( ) ;
            add ( 1 , l , r , x ) ;
        }else {
            l = _c( ) , r = _c( ) ;
            cout << askk ( 1 , l , r ) << endl ;
        }
    }
    return 0 ;
}

by ZYLZPP @ 2024-04-25 19:06:02

mistake1

change中

t[q].flag1 += x ;

改为

t[q].flag1 = x ;

mistake2

add中遍历左右儿子时用了change

改为

if ( l <= mid ) add ( q << 1 , l , r , x ) ;
if ( r > mid ) add ( q << 1 | 1 , l , r , x ) ;

qwq

mistake3

不开 long long 祖宗！！！

flag2和maxx开成long long

struct S{
    int l , r ;
    long long flag2;
    int flag1 , flag3 ;
    long long maxx ;
}t[4*N];

同时将build中maxx初始值赋为-1e18

t[q].flag3 = 0 ;
t[q].maxx = -1e18 ;

注：|a|,|x|<=1e9 不等价于 ans<=1e9

AC code

#include<bits/stdc++.h>
using namespace std ;
#define N 1000005
#define _f(i,a,b) for ( int i = (a) ; i <= (b) ; ++i )
inline int _c ( ){
    int XX=0,FF=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            FF*=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        XX=XX*10+ch-48;
        ch=getchar();
    }
    return XX*FF;
}
int n , qs ;
int a[N] ;
struct S{
    int l , r ;
    long long flag2;
    int flag1 , flag3 ;
    long long maxx ;
}t[4*N];
void Up ( int q ){
    t[q].maxx = max ( t[q<<1].maxx , t[q<<1|1].maxx ) ;
}
void Down ( int q ){
    if ( t[q].flag3 ){
        t[q<<1].flag1 = t[q].flag1 ;
        t[q<<1|1].flag1 = t[q].flag1 ;
        t[q<<1].flag2 = t[q].flag2 ;
        t[q<<1|1].flag2 = t[q].flag2 ;
        t[q<<1].maxx = t[q].flag1 + t[q].flag2 ;
        t[q<<1|1].maxx = t[q].flag2 + t[q].flag1 ;
        t[q<<1].flag3 = t[q<<1|1].flag3 = 1 ;
    }else{
        t[q<<1].flag2 += t[q].flag2 ;
        t[q<<1|1].flag2 += t[q].flag2 ;
        t[q<<1].maxx += t[q].flag2 ;
        t[q<<1|1].maxx += t[q].flag2  ;
    }
    t[q].flag1 = t[q].flag2 = t[q].flag3 = 0 ;
}
void build (int q , int l , int r ){
    t[q].l = l ;
    t[q].r = r ;
    t[q].flag3 = 0 ;
    t[q].maxx = -1e18 ;
    if ( l == r ){
        t[q].maxx = a[l] ;
        return ;
    }
    int mid = ( l + r ) >> 1 ;
    build ( q <<1 , l , mid );
    build ( q<<1|1 , mid + 1 , r ) ;
    Up(q) ;
}
void change ( int q , int l , int r , int x ){
//  cout <<t[q].l << " " << t[q].r << endl ;
    if ( l <= t[q].l && t[q].r <= r ){
        t[q].flag1 = x ;
        t[q].flag2 = 0 ;
        t[q].maxx = x ;
        t[q].flag3 = 1 ;
        return ;
    }
    Down ( q ) ;
    int mid = ( t[q].l + t[q].r ) >> 1 ;
    if ( l <= mid ) change ( q << 1 , l , r , x ) ;
    if ( r > mid ) change ( q << 1 | 1 , l , r , x ) ;
    Up ( q ) ;
}
void add ( int q , int l , int r , int x ){
    if( l <= t[q].l && t[q].r <= r ){
        t[q].flag2 += x ;
        t[q].maxx += x ;
        return ;
    }
    Down ( q ) ;
    int mid = ( t[q].l + t[q].r ) >> 1 ;
    if ( l <= mid ) add ( q << 1 , l , r , x ) ;
    if ( r > mid ) add ( q << 1 | 1 , l , r , x ) ;
    Up (q ) ;
}
long long askk ( int q , int l , int r ){
    if ( l <= t[q].l && t[q].r <= r ){
        return t[q].maxx ;
    }
    Down ( q ) ;
    long long maxn = -1e18 ;
    int mid = ( t[q].l + t[q].r ) >> 1 ; 
    if ( l <= mid ) maxn = max ( maxn , askk ( q<< 1 , l , r ) ) ;
    if ( r > mid ) maxn = max ( maxn , askk ( q << 1 | 1 , l , r  ) ) ;
    return maxn ;
}
int main ( ){
    cin >> n >> qs ;
    _f( i , 1 , n ){
        a[i] = _c( ) ;
    }
    build ( 1 , 1 , n ) ;
    int op ;
    int l , r , x ;
    _f ( i , 1 , qs ){
        op = _c( ) ;
        if ( op == 1 ){
            l = _c( );
            r = _c( );
            x = _c( );

            change ( 1 , l , r , x ) ;
        }else if ( op == 2 ){
            l = _c( ) , r = _c( ) , x = _c( ) ;
            add ( 1 , l , r , x ) ;
        }else {
            l = _c( ) , r = _c( ) ;
            cout << askk ( 1 , l , r ) << endl ;
        }
    }
    return 0 ;
}

by ZYLZPP @ 2024-04-25 19:07:22

@A_chicken_boy

加油

by A_chicken_boy @ 2024-04-25 19:13:17

谢谢dalao，已关