线段树9pts 求调

czy032321054 @ 2024-10-20 23:04:02

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
struct node{
    int l,r,sum,mxl,mxr,mx;
}tree[maxn*4];
int n,m,op,x,y,a[maxn];
void refresh(int now){
    tree[now].mx=max(tree[now*2].mxr+tree[now*2+1].mxl,max(tree[now*2].mx,tree[now*2+1].mx));
    tree[now].mxl=max(tree[now*2].sum+tree[now*2+1].mxl,tree[now*2].mxl);
    tree[now].mxr=max(tree[now*2].mxr+tree[now*2+1].sum,tree[now*2+1].mxr);
    tree[now].sum=tree[now*2].sum+tree[now*2+1].sum;
}
void build(int now,int l,int r){
    tree[now].l=l,tree[now].r=r;
    if(l==r){
        tree[now].mx=a[l];
        tree[now].mxr=a[l];
        tree[now].mxl=a[l];
        tree[now].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    refresh(now);
}
void change(int i,int d,int num){
    if(tree[i].l==tree[i].r){
        tree[i].mx=num;
        tree[i].mxr=num;
        tree[i].mxl=num;
        tree[i].sum=num;
        return;
    }
    if(tree[i*2].r>=d&&d>=tree[i*2].l)
        change(i*2,d,num);
    if(tree[i*2+1].r>=d&&d>=tree[i*2+1].l)
        change(i*2+1,d,num);
    refresh(i);
}
int search(int i,int l,int r){
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].mx;
    int s=-1e9;
    if(tree[i*2].r>=l){
        s=max(s,search(i*2,l,r));
    }
    if(tree[i*2+1].l<=r){
        s=max(s,search(i*2+1,l,r));
    }
    return s;
}
int main(){
    freopen("P4513_2.in","r",stdin);
    freopen("ans.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            if(x>y)swap(x,y);
            printf("%d\n",search(1,x,y));
        }else
            change(1,x,y);
    }
} 

by czy032321054 @ 2024-10-20 23:06:33

@chenxi2009

by czy032321054 @ 2024-10-20 23:40:54

改了一下 但还是没过

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
struct node{
    int l,r,sum,mxl,mxr,mx;
}tree[maxn*4];
int n,m,op,x,y,a[maxn];
void refresh(int now){
    tree[now].mx=max(tree[now*2].mxr+tree[now*2+1].mxl,max(tree[now*2].mx,tree[now*2+1].mx));
    tree[now].mxl=max(tree[now*2].sum+tree[now*2+1].mxl,tree[now*2].mxl);
    tree[now].mxr=max(tree[now*2].mxr+tree[now*2+1].sum,tree[now*2+1].mxr);
    tree[now].sum=tree[now*2].sum+tree[now*2+1].sum;
}
void build(int now,int l,int r){
    tree[now].l=l,tree[now].r=r;
    if(l==r){
        tree[now].mx=tree[now].mxr=tree[now].mxl=tree[now].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    refresh(now);
}
void change(int i,int d,int num){
    if(tree[i].l==tree[i].r){
        tree[i].mx=tree[i].mxr=tree[i].mxl=tree[i].sum=num;
        return;
    }
    if(tree[i*2].r>=d&&d>=tree[i*2].l)
        change(i*2,d,num);
    if(tree[i*2+1].r>=d&&d>=tree[i*2+1].l)
        change(i*2+1,d,num);
    refresh(i);
}
node search(int i,int l,int r){
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i];
    int s=0;
    if(tree[i*2].r>=l){
        return search(i*2,l,r);
    }else if(tree[i*2+1].l<=r){
        return search(i*2+1,l,r);
    }else{
        node t,ls=search(i*2,x,y),rs=search(i*2+1,x,y);
        t.mxl=max(ls.mxl,ls.sum+rs.mxl);
        t.mxr=max(rs.mxr,ls.mxr+rs.sum);
        t.mx=max(max(ls.mx,rs.mx),ls.mxr+rs.mxl);
        t.sum=ls.sum+rs.sum;
        return t;
    }
}
int main(){
//  freopen("P4513_2.in","r",stdin);
//  freopen("ans.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            if(x>y)swap(x,y);
            printf("%d\n",(search(1,x,y).mx));
        }else
            change(1,x,y);
    }
} 

by czy032321054 @ 2024-10-20 23:58:02

okkk

此帖结