线段树0分，求调

zhangsiyu2304 @ 2024-07-25 11:08:46

#include <iostream> 
#define now (st[u])
#define left (st[u<<1])
#define right (st[(u<<1)+1])
using namespace std;
int n,m,opt,x,y,k,a[100001];
struct STNode{
    int l,r,lazy;
    long long sum;
} st[400001];
void build(int u,int l,int r){
    now.l=l;now.r=r;
    if (l!=r){
        int mid=(l+r)>>1;
        build(u<<1,l,mid);
        build((u<<1)+1,mid+1,r);
        now.sum=left.sum+right.sum;
    }else{
        now.sum=a[l];
    }
}
void pushdown(int u){
    if (now.lazy){
        left.lazy+=now.lazy;
        right.lazy+=now.lazy;
        now.sum+=now.lazy*(now.r-now.l+1);
        now.lazy=0;
    }
}
void modify(int u,int l,int r,int k){
    if (l<=now.l&&now.r<=r) now.lazy+=k;
    else if (now.r<l||now.l>r) return;
    else{
        int mid=(now.l+now.r)/2;
        if (l<=mid) modify(u<<1,l,r,k);
        if (r>mid) modify((u<<1)+1,l,r,k);
    }
}
int query(int u,int l,int r){
    if (now.r<l||now.l>r) return 0;
    pushdown(u);
    if (l<=now.l&&now.r<=r) return now.sum;
    int ans=0,mid=(now.l+now.r)/2;
    if (l<=mid) ans+=query(u<<1,l,r);
    if (r>mid) ans+=query((u<<1)+1,l,r);
    return ans;
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for (int i=1;i<=m;i++){
        cin>>opt;
        if (opt==1) cin>>x>>y>>k;
        else cin>>x>>y;
        if (opt==1) modify(1,x,y,k);
        else cout<<query(1,x,y)<<'\n';
    }
    return 0;
}

by __cheng827922__ @ 2024-07-25 11:22:19

#include<iostream>
#include<cstdio>
#define MAXN 1000001
#define ll long long
using namespace std;
unsigned ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
inline ll ls(ll x)
{
    return x<<1;
}
inline ll rs(ll x)
{
    return x<<1|1;
}
void scan()
{
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    scanf("%lld",&a[i]);
}
inline void push_up(ll p)
{
    ans[p]=ans[ls(p)]+ans[rs(p)];
}
void build(ll p,ll l,ll r)
{
    tag[p]=0;
    if(l==r){ans[p]=a[l];return ;}
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
} 
inline void f(ll p,ll l,ll r,ll k)
{
    tag[p]=tag[p]+k;
    ans[p]=ans[p]+k*(r-l+1);
}
inline void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
    if(nl<=l&&r<=nr)
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return ;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
    ll res=0;
    if(q_x<=l&&r<=q_y)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(q_x<=mid)res+=query(q_x,q_y,l,mid,ls(p));
    if(q_y>mid) res+=query(q_x,q_y,mid+1,r,rs(p));
    return res;
}
int main()
{
    ll a1,b,c,d,e,f;
    scan();
    build(1,1,n);
    while(m--)
    {
        scanf("%lld",&a1);
        switch(a1)
        {
            case 1:{
                scanf("%lld%lld%lld",&b,&c,&d);
                update(b,c,1,n,1,d);
                break;
            }
            case 2:{
                scanf("%lld%lld",&e,&f);
                printf("%lld\n",query(e,f,1,n,1));
                break;
            }
        }
    }
    return 0;
}

by Rice_Demon_King @ 2024-07-25 11:29:50

已修改，见注释

#include <iostream> 
#define now (st[u])
#define left (st[u<<1])
#define right (st[(u<<1)+1])
using namespace std;
int n,m,opt,x,y,k;
long long a[200001];    //洛谷数据特性：刚好卡死会RE,所以记得多开一点 
struct STNode{
    int l,r;
    long long lazy,sum;     //懒标记开到long long会保险，有可能k很大 
} st[800001];
void build(int u,int l,int r){
    now.l=l;now.r=r;
    if (l!=r){
        int mid=(l+r)>>1;
        build(u<<1,l,mid);
        build((u<<1)+1,mid+1,r);
        now.sum=left.sum+right.sum;
    }else{
        now.sum=a[l];
    }
}
void pushdown(int u){
    if (now.lazy){
        left.lazy+=now.lazy;
        right.lazy+=now.lazy;
        left.sum+=now.lazy*(left.r-left.l+1);           //更新左区间 
        right.sum+=now.lazy*(right.r-right.l+1);        //更新右区间 
        now.lazy=0ll;
    }
}
void modify(int u,int l,int r,long long k){
    if (l<=now.l&&now.r<=r){
        now.lazy+=k;
        now.sum+=(now.r-now.l+1)*k;         //now的区间和同步更新 
    } 
    else if (now.r<l||now.l>r) return;
    else{
        pushdown(u);        //修改子区间时也要实时更新 
        int mid=(now.l+now.r)/2;
        if (l<=mid) modify(u<<1,l,r,k);
        if (r>mid) modify((u<<1)+1,l,r,k);
        now.sum=left.sum+right.sum;     //修改完后也要对now更新 
    }
}
long long query(int u,int l,int r){         //查出来的值也是long long类型的 
    if (now.r<l||now.l>r) return 0ll;
    pushdown(u);
    if (l<=now.l&&now.r<=r) return now.sum;
    long long ans=0ll;
    int mid=(now.l+now.r)/2;        //ans是long long类型的 
    if (l<=mid) ans+=query(u<<1,l,r);
    if (r>mid) ans+=query((u<<1)+1,l,r);
    return ans;
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout,tie(0); 
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for (int i=1;i<=m;i++){
        cin>>opt;
        if (opt==1) cin>>x>>y>>k;
        else cin>>x>>y;
        if (opt==1) modify(1,x,y,k);
        else cout<<query(1,x,y)<<'\n';
    }
    return 0;
}

求关注awa

by zhangsiyu2304 @ 2024-07-25 11:36:18

@Rice_Demon_King 谢谢