求调

P3372 【模板】线段树 1

Ji_Ye @ 2023-08-13 00:08:45

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll tr[1000];    
ll n,m;
ll cz,x,y,e,f,q;
ll a[1000];
ll tag[1000];
void push_up_sum(ll p)
{
    tr[p]=tr[2*p]+tr[2*p+1];
}
/*
void push_up_min(ll p)
{
    tr[p]=min or max(tr[2*p],tr[2*p+1]);

*/
void biuld(ll num,ll l,ll r)
{
    if(l==r)
    {
        tr[num]=a[l];
    }
    ll mid=(l+r)>>1;
    biuld(2*num,l,mid);
    biuld(((2*num)|1),mid+1,r);
}
int ff(ll p,ll l,ll r,ll k)
{
    tag[p]+=k;
    tr[p]=tr[p]+(r-l+1)*k;
}
void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    ff(2*p,l,mid,tag[p]);
    ff((2*p)|1,mid+1,r,tag[p]);
    tag[p]=0;
}
void update(ll stl,ll str,ll l,ll r,ll p,ll k)
{
    if(stl<=l&&str<=r)
    {
        tr[p]+=k*(r-l+1);
        tag[p]+=k;
        return;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(stl<=mid)
    update(stl,str,l,mid,2*p,k);
    if(str>mid) 
    update(stl,str,mid+1,r,2*p|1,k);
    push_up_sum(p);
}
ll lk_for(ll nx,ll ny,ll l,ll r,ll p)
{
    ll cnt=0;
    if(nx<=l&&r<=ny)
    {
        return tr[p];
    }
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(nx<=mid)
    cnt+=lk_for(nx,ny,l,mid,2*p);
    if(ny>mid) 
    cnt+=lk_for(nx,ny,mid+1,r,2*p|1);
    return cnt;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    biuld(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>cz;
        if(cz==1)
        {
            cin>>x>>y>>q;
            update(x,y,1,n,1,q);
        }
        if(cz==2)
        {
            cin>>e>>f;
            int out=lk_for(e,f,1,n,1);
            cout<<out;
            cout<<endl;
        }

    }
    return 0;
}

蒟蒻不知道要怎么改了


by OldDriverTree @ 2023-08-13 00:31:41

@SBSBismy 提交记录?


by 8atemak1r @ 2023-08-13 01:35:41

@SBSBismy

  1. 数组开太小了,看数据范围
  2. buildif 里面应该 return
  3. update 里面 if 的条件错了

|