记录编号	582298	评测结果	AAAAAAAAAA
题目名称	Can you answer these queries III	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.797 s
提交时间	2023-09-08 20:12:03	内存使用	48.08 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 5e5+10;
int n,m;
int a[N];
struct made{
    int l,r;
    int sum,lm,rm,len;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define sum(x) t[x].sum
    #define lm(x) t[x].lm
    #define rm(x) t[x].rm
    #define len(x) t[x].len
}t[N<<2];
void pushup(int x){
    sum(x) = sum(x<<1) + sum(x<<1|1);
    lm(x) = max(lm(x<<1),sum(x<<1)+lm(x<<1|1));
    rm(x) = max(rm(x<<1|1),sum(x<<1|1)+rm(x<<1));
    len(x) = max(max(len(x<<1),len(x<<1|1)),rm(x<<1)+lm(x<<1|1));
}
void build(int x,int l,int r){
    l(x) = l,r(x) = r;
    if(l == r){
        sum(x) = lm(x) = rm(x) = len(x) = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void add(int x,int l,int ed){
    if(l(x) == r(x) && l(x) == l){
        sum(x) = lm(x) = rm(x) = len(x) = ed;
        return;
    }
    t[x];
    int mid = (l(x) + r(x)) >> 1;
    if(l <= mid)add(x<<1,l,ed);
    else add(x<<1|1,l,ed);
    pushup(x);
}
made ask(int x,int l,int r){
    if(l <= l(x) && r(x) <= r)return t[x];
    int mid = (l(x) + r(x)) >> 1;
    if(mid >= r)return ask(x<<1,l,r);
    if(mid < l)return ask(x<<1|1,l,r);
    made a = ask(x<<1,l,mid),b = ask(x<<1|1,mid+1,r),c;
    c.sum = a.sum + b.sum;
    c.lm = max(a.lm,a.sum+b.lm);
    c.rm = max(b.rm,b.sum+a.rm);
    c.len = max(max(a.len,b.len),a.rm+b.lm);
    return c;
}
int main(){
    freopen("GSS_3.in","r",stdin);
    freopen("GSS_3.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    for(int i = 1;i <= m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(x == 1){
            if(y > z)swap(y,z);
            printf("%d\n",ask(1,y,z).len);
        }
        else add(1,y,z);
    }
    
    return 0;
    
}