求助 9 分线段树

UperFicial @ 2021-07-18 13:57:19

by UperFicial @ 2021-07-18 13:57:37

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<climits>
using namespace std;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0' or ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' and ch<='9')s=s*10+(ch-'0'),ch=getchar();
    return s*w;
}
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline void Swap(int&x,int&y){x^=y;y^=x;x^=y;}
const int MAXM(5e5+10);
const int MAXN(MAXM*4);
int n,m,a[MAXM];
int lc[MAXN],rc[MAXN],sum[MAXN],maxl[MAXN],maxr[MAXN],maxv[MAXN];
inline void push_up(int u)
{
    sum[u]=sum[lc[u]]+sum[rc[u]];
    maxl[u]=sum[lc[u]]+maxl[rc[u]];
    maxr[u]=maxr[lc[u]]+sum[rc[u]];
    maxv[u]=Max(Max(maxv[lc[u]],maxv[rc[u]]),maxr[lc[u]]+maxl[rc[u]]);
    return;
}
inline void build(int u,int l,int r)
{
    if(l==r)
    {
        sum[u]=maxv[u]=maxl[u]=maxr[u]=a[l];
        return;
    }
    lc[u]=u<<1,rc[u]=u<<1|1;
    int mid=(l+r)>>1;
    build(lc[u],l,mid);
    build(rc[u],mid+1,r);
    push_up(u);
    return;
}
inline void update(int u,int l,int r,int p,int k)
{
    if(l==p&&r==p)
    {
        sum[u]=maxv[u]=maxl[u]=maxr[u]=k;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(lc[u],l,mid,p,k);
    else update(rc[u],mid+1,r,p,k);
    push_up(u);
    return;
}
inline int query(int u,int l,int r,int ln,int rn)
{
    int res(INT_MIN);
    if(ln<=l&&r<=rn) return maxv[u];
    int mid=(l+r)>>1;
    if(ln<=mid) res=Max(res,query(lc[u],l,mid,ln,rn));
    else if(rn>mid) res=Max(res,query(rc[u],mid+1,r,ln,rn));
    return res;
}
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    while(m--)
    {
        int opt=read();
        if(opt==1) 
        {
            int l=read(),r=read();
            if(l>r) Swap(l,r);
            printf("%d\n",query(1,1,n,l,r));
        }
        else
        {
            int p=read(),k=read();
            update(1,1,n,p,k);
        }
    }
    return 0;
}

by SSL_wj @ 2021-07-18 14:45:20

本题必须使用结构体，因为查询时访问的是子节点的一部分，本题区间不能分裂只能合并

by SSL_wj @ 2021-07-18 14:50:03

@UperFicial

by UperFicial @ 2021-07-18 15:24:04

@SSL_wj 改成结构体还是 9pts/ll

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<climits>
using namespace std;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0' or ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' and ch<='9')s=s*10+(ch-'0'),ch=getchar();
    return s*w;
}
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline void Swap(int&x,int&y){x^=y;y^=x;x^=y;}
const int MAXM(5e5+10);
const int MAXN(MAXM*4);
int n,m,a[MAXM];
struct Segment
{
    int maxl,maxr,sum,maxv;
};
Segment tree[MAXN];
inline int lc(int u){return u<<1;}
inline int rc(int u){return u<<1|1;}
inline void push_up(int u)
{
    tree[u].sum=tree[lc(u)].sum+tree[rc(u)].sum;
    tree[u].maxl=tree[lc(u)].sum+tree[rc(u)].maxl;
    tree[u].maxr=tree[lc(u)].maxr+tree[rc(u)].sum;
    tree[u].maxv=Max(tree[lc(u)].maxr+tree[rc(u)].maxl,Max(tree[lc(u)].maxv,tree[rc(u)].maxv));
    return;
}
inline void putval(int u,int v)
{
    tree[u].sum=tree[u].maxv=tree[u].maxl=tree[u].maxr=v;
    return;
}
inline void build(int u,int l,int r)
{
    if(l==r){putval(u,a[l]);return;}
    int mid=(l+r)>>1;
    build(lc(u),l,mid);
    build(rc(u),mid+1,r);
    push_up(u);
    return;
}
inline void update(int u,int l,int r,int p,int k)
{
    if(l==p&&r==p)
    {
        putval(u,k);
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(lc(u),l,mid,p,k);
    else update(rc(u),mid+1,r,p,k);
    push_up(u);
    return;
}
inline int query(int u,int l,int r,int ln,int rn)
{
    int res(INT_MIN);
    if(ln<=l&&r<=rn) return tree[u].maxv;
    int mid=(l+r)>>1;
    if(ln<=mid) res=Max(res,query(lc(u),l,mid,ln,rn));
    else if(rn>mid) res=Max(res,query(rc(u),mid+1,r,ln,rn));
    return res;
}
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    while(m--)
    {
        int opt=read();
        if(opt==1) 
        {
            int l=read(),r=read();
            if(l>r) Swap(l,r);
            printf("%d\n",query(1,1,n,l,r));
        }
        else
        {
            int p=read(),k=read();
            update(1,1,n,p,k);
        }
    }
    return 0;
}

by mod998244353 @ 2021-07-18 16:46:55

@UperFicial push_up中，更新tree[u].maxl应为：

tree[u].maxl=max(tree[lc(u)].maxl,tree[lc(u)].sum+tree[rc(u)].maxl);

tree[u].maxr同理

by UperFicial @ 2021-07-18 16:51:06

@mod998244353 感谢