线段树求调

#include<bits/stdc++.h>
using namespace std;
long long n,a[222222],dp[222222][2],t[888888],ma=-0x16f,m,l,r,k,laz[888888];
void push_up(long long k)
{
    t[k]=t[k*2]+t[k*2+1];
}
void build(long long k,long long l,long long r)
{
    if(l==r)t[k]=a[l];
    else
    {
        long long mid=(l+r)/2;
        build(k*2,l,mid);
        build(k*2+1,mid+1,r);
        push_up(k);
    }
}
void tag(long long k,long long l,long long r,long long v)
{
    laz[k]+=v;
    t[k]+=(r-l+1)*v;
}
void push_down(long long k,long long l,long long r)
{
    if(!laz[k])return;
    long long mid=(l+r)/2;
    tag(k*2,l,mid,laz[k]);
    tag(k*2+1,mid+1,r,laz[k]);
    laz[k]=0;
}
void update(long long x,long long y,long long v,long long l,long long r,long long k)
{
    if(x<=l&&y>=r)
    {
        tag(k,l,r,v);
        return;
    }
    long long mid=(l+r)/2;
    push_down(k,l,r);
    if(x<=mid)update(x,y,v,l,mid,k*2);
    if(y>mid)update(x,y,v,mid+1,r,k*2+1);
    push_up(k);
}
long long query(long long x,long long y,long long l,long long r,long long k)
{
    if(x<=l&&y>=r)return t[k];
    long long res=0,mid=(l+r)/2;
    push_down(k,l,r);
    if(x<=mid)res=max(res,query(x,y,l,mid,k*2));
    if(y>mid)res=max(res,query(x,y,mid+1,r,k*2+1));
    return res;
}
int main()
{
    cin>>n>>m;
    build(1,1,n);
    for(long long i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",bitand k,bitand l,bitand r);
        if(k==1)update(1,n,1,l,r,1);
        else printf("%lld\n",query(l,r,1,n,1));
    } 
    return 0;
}

4 条评论

  • 1

信息

ID
1448
难度
6
分类
数据结构 | 线段树 点击显示
标签
递交数
2933
已通过
876
通过率
30%
被复制
6
上传者