菜菜求助,只能过3#案例,不知道代码哪里有问题

P3372 【模板】线段树 1

kangkang0201 @ 2023-08-21 00:02:51

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ll long long
unsigned ll a[MAXN];
struct node
{
    int l,r;
    ll lazy;
    ll sum;
}tr[MAXN<<2|4];
//整合
inline void pushup(int u)
{
    tr[u].sum = tr[u<<1].sum  +  tr[u<<1|1].sum;
}
void buildtree(int u , int l , int r)
{
    tr[u].l = l;
    tr[u].r = r;
    if(l == r)
    {
        tr[u].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    buildtree(u<<1,l,mid);
    buildtree(u<<1|1,mid+1,r);
    pushup(u);

}
//如果查询的节点在之前放置的懒标记之下
inline void pushdown(int u)
{
    if(tr[u].lazy)
    {
        tr[u<<1].lazy = tr[u].lazy;
        tr[u<<1].sum += (tr[u<<1].r - tr[u<<1].l + 1)*tr[u].lazy;
        tr[u<<1|1].lazy = tr[u].lazy;
        tr[u<<1|1].sum += (tr[u<<1|1].r -tr[u<<1|1].l + 1)*tr[u].lazy;
        tr[u].lazy = 0;
    }
}
inline void modify(int u ,int l ,int r, ll k)
{
    if(l<= tr[u].l && r >= tr[u].r)
    {
        tr[u].lazy += k;
        tr[u].sum +=(tr[u].r - tr[u].l + 1) * k;
        return;
    }
    //先把懒标记更新下去
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid)
    {
        modify(u<<1,l,mid,k);
    }
    if(r > mid)
    {
        modify(u<<1|1,mid+1,r,k);
    }
    pushup(u);

}
ll query(int u ,int l ,int r)
{
    if(l <= tr[u].l && r>=tr[u].r)
    {
        return tr[u].sum;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >>1;
    ll res = 0;
    if(l <= mid) res+= query(u<<1 , l, r);
    if(r > mid) res+= query(u<<1|1, l, r);
    return res;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ; i++)
    {
        cin>>a[i];
    }
    buildtree(1,1,n);
    for(int i = 0 ; i < m ;i++)
    {
        int stra;
        cin>>stra;
        if(stra == 1)
        {
            int l, r;
            ll k;
            cin>>l>>r>>k;
            modify(1,l,r,k);
        }
        else
        {
            int l,r;
            cin>>l>>r;
            ll answer = query(1,l,r);
            printf("%lld\n",answer);

        }
    }
    return 0;

}

by DGME @ 2023-08-21 02:12:26


|