蒟蒻刚学线段树,仅过样例0ptsRE+WA求调!
查看原帖
蒟蒻刚学线段树,仅过样例0ptsRE+WA求调!
950927
_luo_gu楼主2024/3/7 20:30

以下代码:

#include <bits/stdc++.h>
#define int long long
#define lson ( pos << 1 ) 
#define rson ( pos << 1 | 1 )
using namespace std ;
int res , n , m , a[100005] , opt , L , R , K , D , P ;
//记录差分和lazy tag
struct SegTree {
    int dif ;
    int lz ;
};
SegTree tre[1000005] ;
void pushup( int pos ){
    tre[pos].dif = tre[lson].dif + tre[rson].dif ;
    return ;
}
void build( int pos , int l , int r ){
    //对于线段树进行初始的赋值
    if( l == r ){
        tre[pos].dif = a[l] - a[l-1] ;
        return ;
    }
    int mid = ( l + r ) >> 1 ;
    build( lson , l , mid );
    build( rson , mid+1 ,r );
    pushup( pos );
    return ;
}
void pushdown( int pos , int l , int r ){
    if( l == r ){
        return ;
    }
    //下传lazy tag
    if( tre[pos].lz != 0 ){
        int mid = ( l + r ) >> 1 ;
        
        tre[lson].lz = tre[pos].lz + tre[lson].lz ;

        tre[rson].lz = tre[pos].lz + tre[rson].lz ;
        tre[lson].dif += ( mid - l + 1 ) * tre[pos].lz ;
        tre[rson].dif += ( r - mid ) * tre[pos].lz ;
    } //cout << "test110" <<endl;
    tre[pos].lz = 0 ;
    return ;
}
//单点修改,用于修改首项和末项
void only_change( int pos , int l , int r , int i , int x ){

    //若碰到叶子节点则加上值
    if( l == r && l == i ){
        tre[pos].dif += x ;
        return ;
    }
    pushdown( pos , l , r );
    int mid = ( l + r ) >> 1 ;
    //寻找要修改的叶子节点
    if( i <= mid ){
        only_change( lson , l , mid , i , x );
    }
    if( i > mid ){
        only_change( rson , mid + 1 , r , i , x );
    }
    pushup( pos );
    return ;
}
void both_change( int pos , int l , int r , int ql , int qr , int d){
    //若此区间被包含
    if( ql <= l && qr >= r  ){
        tre[pos].dif = tre[pos].dif + ( r - l + 1 ) * d ;
        tre[pos].lz = tre[pos].lz + d ;
        return ;
    }
    int mid = ( l + r ) >> 1 ;
    //若此区间未被包含
    if( ql <= mid ){
        both_change( lson , l , mid , ql , qr , d );
    }
    if( qr > mid ){
        both_change( rson , mid+1 , r , ql , qr , d );
    }
    pushup( pos );
    return ;
}
//查询
int query( int pos , int l , int r , int x ){
    if( r <= x ){
        res = res + tre[pos].dif ;
        return res ;
    }
    pushdown( pos , l , r );
    int mid = ( l + r ) >> 1 ;
    if( x <= mid ){
        res = res + query( lson , l , mid , x );
    }
    if( x > mid ){
        res = res + query( rson , mid+1 , r , x );
    }
    return res ;
}
signed main(){
    scanf("%lld%lld" , &n , &m );
    for( int i = 1 ; i <= n ; i ++ ){
        scanf("%lld" , &a[i] );
    }
    //m次询问
    while( m -- ){
        scanf("%lld" , &opt );
        if( opt == 1 ){
            scanf("%lld%lld%lld%lld" ,&L , &R , &K , &D );
            //手动修改首项
            //only_change( 1 , 1 , n , L , K );
            //区间修改
            both_change( 1 , 1 , n , L+1 , R , D );
            
            int sub = 0 ;
            sub = K + ( R - L + 1 ) * D ;
            sub = sub * -1 ;
            //手动修改末尾
            only_change( 1 , 1 , n , R+1 , sub ) ;
            
        }
        if( opt == 2 ){
            res = 0 ;
            scanf("%lld" , &P );
            res = query( 1, 1 , n , P );
            printf("%lld\n" , res );
        }
    }
    return 0 ;
}
/*
10 2
200 200 200 200 200 200 200 200 200 200 
1 1 10 200 200
2 100000
*/

感谢大佬!好人一生平安

2024/3/7 20:30
加载中...