萌新刚学 OI ,求助线段树板题

P4513 小白逛公园

MSqwq @ 2021-03-08 13:59:31

QWQ

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n,m,a[8000000];
ll op,x,y;
struct qwe{
    ll l,r;
    ll l1,r1,sum,ma;
}t[8000000];

void pu(ll p)
{
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    t[p].l1=max(t[p*2].l1,t[p*2].sum+t[p*2+1].l1);
    t[p].r1=max(t[p*2+1].r1,t[p*2+1].sum+t[p*2].r1);
    t[p].ma=max(t[p*2].ma,max(t[p*2+1].ma,t[p*2].r1+t[p*2+1].l1));
}

void build(ll p,ll x,ll y)
{
    t[p].l=x;
    t[p].r=y;
    if(x==y)
    {
        t[p].l1=t[p].r1=t[p].sum=t[p].ma=a[x];
        return;
    }

    build(p*2,x,(x+y)/2);
    build(p*2+1,(x+y)/2+1,y);
    pu(p);
}

void insert(ll p,ll x,ll y)
{
    if(t[p].l==t[p].r)
    {
        t[p].l1=t[p].r1=t[p].ma=t[p].sum=y;
        return;
    }
    ll mm=(t[p].l+t[p].r)/2;
    if(x<=mm)insert(p*2,x,y);
    else insert(p*2+1,x,y);
    pu(p);
}

qwe ask(ll p,ll x,ll y)
{
    if(x<=t[p].l&&t[p].r<=y)return t[p];
    ll mm=(t[p].l+t[p].r)/2;

    if(y<=mm)return ask(p*2,x,y);
    else 
    {
        if(x>mm)return ask(p*2+1,x,y);
        else 
        {
            qwe xx,tmp1=ask(p*2,x,y),tmp2=ask(p*2+1,x,y);
            xx.l1=max(tmp1.l1,tmp1.sum+tmp2.l1);
            xx.r1=max(tmp2.r1,tmp2.sum+tmp1.r1);
            xx.ma=max(tmp1.ma,max(tmp2.ma,tmp1.r1+tmp2.l1));
            return xx;
        }
    }
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);

    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1)x=min(x,y),y=max(x,y),printf("%lld\n",ask(1,x,y).ma);
        else insert(1,x,y);
    }
}

by Macesuted @ 2021-03-08 14:57:07

x=min(x,y),y=max(x,y) 这个信息会被覆盖。


by Lucifero @ 2021-03-08 15:15:22

%%%


by Lucifero @ 2021-03-08 15:41:44

@My_sort

swap(x,y)

Macesuted


by zhangboju @ 2021-03-08 16:26:58

就是说 if(op==1)x=min(x,y),y=max(x,y),printf("%lld\n",ask(1,x,y).ma);

大概改成

if(op==1)
{
    if(x>y) swap(x,y);
   printf("%lld\n",ask(1,x,y).ma);
}

by MSqwq @ 2021-03-08 21:45:30

@Gray_White 谢谢


by MSqwq @ 2021-03-08 21:45:55

@zhangboju 谢谢qwq


by MSqwq @ 2021-03-08 21:50:45

@Macesuted 谢谢呀qwq


|