求助

回复帖子

@无敌的蒟蒻  2020-02-14 22:11 回复

有什么讲线段树很详细的博客?里面要有区间最大子段和之类的

@liqingyang 2020-02-14 23:15 回复 举报

这是我单点修改最大值的代码

#include<iostream>
using namespace std;
const long long oo=(long long)1e18;
long long a[300010];
int n,m;
void update(int s)
{
    a[s]=max(a[s*2],a[s*2+1]);
}
void biuld(int l,int r,int s)
{
    if(l==r)
    {
        cin>>a[s];
        return;
    }
    int mid=(l+r)/2;
    biuld(l,mid,s*2);
    biuld(mid+1,r,s*2+1);
    update(s);
}
void change(int l,int r,int s,int x,long long y)
{
    if(r<x||l>x)
    {
        return;
    }
    if(x==l&&x==r)
    {
        a[s]=y;
        return;
    }
    int mid=(l+r)/2;
    change(l,mid,s*2,x,y);
    change(mid+1,r,s*2+1,x,y);
    update(s);
}
long long q(int l,int r,int ll,int rr,int s)
{
    if(r<ll||l>rr)
    {
        return -oo;
    }
    if(ll<=l&&r<=rr)
    {
        return a[s];
    }
    int mid=(l+r)/2;
    return max(q(l,mid,ll,rr,s*2),q(mid+1,r,ll,rr,s*2+1));
}
int main()
{
    freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    cin>>n;
    biuld(1,n,1);
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int flag,x;
        long long y;
        cin>>flag>>x>>y;
        if(flag==1)
        {
            change(1,n,1,x,y);
        }
        else
        {
            cout<<q(1,n,x,y,1)<<endl;
        }
    }
    return 0;
}
@liqingyang 2020-02-14 23:18 回复 举报

这是我多点修改最大值的代码

#include<iostream>
#include<algorithm>
using namespace std;
const long long oo=(long long)1e18;
struct tree
{
    long long x;
    int ss;
};
tree a[300010];
int n,m;
void update(int s)
{
    a[s].x=max(a[s*2].x,a[s*2+1].x);
}
void pushdown(int s)
{
    if(a[s].ss)
    {
        a[s*2].ss+=a[s].ss;
        a[s*2+1].ss+=a[s].ss;
        a[s*2].x+=a[s].ss;
        a[s*2+1].x+=a[s].ss;
        a[s].ss=0;
    }
}
void biuld(int l,int r,int s)
{
    if(l==r)
    {
        cin>>a[s].x;
        return;
    }
    int mid=(l+r)/2;
    biuld(l,mid,s*2);
    biuld(mid+1,r,s*2+1);
    update(s);
}
void add(int l,int r,int ll,int rr,int c,int s)
{
    if(r<ll||l>rr)
    {
        return;
    }
    if(ll<=l&&r<=rr)
    {
        a[s].x+=c;
        a[s].ss+=c;
        return;
    }
    pushdown(s);
    int mid=(l+r)/2;
    add(l,mid,ll,rr,c,s*2);
    add(mid+1,r,ll,rr,c,s*2+1);
    update(s);
}
long long getans(int l,int r,int ll,int rr,int s)
{
    if(r<ll||l>rr)
    {
        return -oo;
    }
    if(ll<=l&&r<=rr)
    {
        return a[s].x;
    }
    pushdown(s);
    int mid=(l+r)/2;
    return max(getans(l,mid,ll,rr,s*2),getans(mid+1,r,ll,rr,s*2+1));
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    biuld(1,n,1);
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int flag,x,y;
        cin>>flag>>x>>y;
        if(flag==1)
        {
            int v;
            cin>>v;
            add(1,n,x,y,v,1);
        }
        else
        {
            cout<<getans(1,n,x,y,1)<<endl;
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。