9pts 求调，调一天了qwq

QWQ_SenLin @ 2023-07-23 15:09:39

by QWQ_SenLin @ 2023-07-23 15:09:52

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

int n , m;
long long a[2000005];

struct Tree {
    long long sum , lmax , rmax , max;
    Tree(){
        sum = lmax = rmax = max = 0;
    }
}qwq[2000005];

void pushup(int p){
    qwq[p].sum = qwq[p << 1].sum + qwq[p << 1 | 1].sum;
    qwq[p].max = qwq[p << 1].rmax + qwq[p << 1 | 1].lmax;
    qwq[p].max = max(qwq[p].max , qwq[p << 1].max);
    qwq[p].max = max(qwq[p].max , qwq[p << 1 | 1].max);
    qwq[p].lmax = max(qwq[p << 1].lmax , qwq[p << 1].sum + qwq[p << 1 | 1].lmax);
    qwq[p].rmax = max(qwq[p << 1 | 1].rmax , qwq[p << 1 | 1].sum + qwq[p << 1].rmax);
}

void init(int p , int l , int r){
    if(l == r){
        qwq[p].sum = qwq[p].max = qwq[p].lmax = qwq[p].rmax = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    init(p << 1 , l , mid);
    init(p << 1 | 1 , mid + 1 , r);
    pushup(p);
}

void upd(int p , int l , int r , int x , long long y){
    if(l == r && l == x){
        qwq[p].sum = qwq[p].max = qwq[p].lmax = qwq[p].rmax = y;
        return ;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)
        upd(p << 1 , l , mid , x , y);
    else
        upd(p << 1 | 1 , mid + 1 , r , x , y);
    pushup(p);
}

Tree get(int p , int l , int r , int x , int y){
    if(l >= x && r <= y)    
        return qwq[p]; 
    int mid = (l + r) >> 1;
    if(y <= mid)
        return get(p << 1 , l , mid , x , y);
    if(x > mid)
        return get(p << 1 | 1 , mid + 1 , r , x , y);
    Tree lson = get(p << 1 , l , mid , x , y);
    Tree rson = get(p << 1 | 1 , mid + 1 , r , x , y);
    Tree ret;
    ret.max = lson.rmax + rson.lmax;
    ret.max = max(ret.max , lson.max);
    ret.max = max(ret.max , rson.max);
    ret.rmax = max(lson.lmax , lson.sum + rson.lmax);
    ret.rmax = max(rson.rmax , rson.sum + lson.rmax);
    return ret;
}

int main(void){
    scanf("%d%d" , &n , &m);
    for(int i = 1;i <= n;i++)
        scanf("%lld" , &a[i]);
    init(1 , 1 , n);
    while(m--){
        long long op , x , y;
        scanf("%lld%lld%lld" , &op , &x , &y);
        if(op == 1){
            if(x > y)
                swap(x , y);
            printf("%lld\n" , get(1 , 1 , n , x , y).max);  
        }
        else
            upd(1 , 1 , n , x , y);
    }
}

by QWQ_Frieren @ 2023-07-24 09:13:57

鸡你太美

by QWQ_SenLin @ 2023-07-24 09:41:45

已AC，把 l 打成 r 了。。

by huangluyi2008 @ 2023-07-24 10:10:40

%%%

by Ghtl @ 2024-04-11 12:53:07

%%%