30分悬关求调

紫玄月 @ 2024-03-03 12:07:30

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 4 * 2000010;
ll n, m, a[maxn], sum[maxn], addv[maxn];
//ll l, r;
void build(ll o,ll l,ll r){
    if(l==r){
        sum[o]=a[l];
        return;
    }
    ll lc=2*o,rc=2*o+1;
    ll c=l+(r-l)/2;
    build(lc,l,c);
    build(rc,c+1,r);
    sum[o]=sum[lc]+sum[rc];
}
void maintain(ll o,ll l,ll r){
    ll lc=2*o,rc=2*o+1;
    if(r>l)
        sum[o]=sum[lc]+sum[rc];
    sum[o]+=addv[o]*(r-l+1);
}
ll ql,qr,v;
void update(ll o,ll l,ll r){
    ll lc=2*o,rc=2*o+1;
    ll c=l+(r-l)/2;
    if(ql<=l&&qr>=r){
        addv[o]+=v;
    }
    else{
        if(ql<=c)
            update(lc,l,c);
        if(qr>c)
            update(rc,c+1,r);
    }
    maintain(o,l,r);
}
ll sumv;
void query(ll o,ll l,ll r,ll add){
    ll c=l+(r-l)/2;
    ll lc=2*o,rc=2*o+1;
    if(ql<=l&&qr>=r)
        sumv+=sum[o]+add*(r-l+1);
    else{
        if(ql<=c)
            query(lc,l,c,addv[o]+add);
        if(qr>c)
            query(rc,c+1,r,addv[o]+add);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);   
    while(m--){
        ll f;
        cin>>f>>ql>>qr;
        if(f==1){
            cin>>v;
            update(1,1,n);
        }
        if(f==2){
            sumv=0;
            query(1,1,n,0);
            cout<<sumv<<endl;
        }
    }
    return 0;
}

by cj180202 @ 2024-03-03 12:12:29

你压根没有下传懒惰标啊？

by 紫玄月 @ 2024-03-03 12:12:31

前几个点都能对，第四个点在第62行的时候答案差了几十，到后面越差越大。感觉可能是边界的处理问题，但我查不出来bug在哪里。

by cj180202 @ 2024-03-03 12:13:41

而且query的add我不理解为什么要在调用时做加法，你的实现方式太小众导致很难调。

by 紫玄月 @ 2024-03-03 12:16:07

知道了，谢谢

by cj180202 @ 2024-03-03 12:20:12

@紫玄月

你看一下我这样的实现方式。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mxn=1e5;
int n,q,opt,l,r,x,a[mxn+5];
struct segtree{//用结构体保存每个区间的信息
    int l,r,sum,lazy;//lazy为加法懒惰标
}t[4*mxn+5];
void build(int p,int l,int r){
    int ls,rs,mid;
    ls=p*2;rs=p*2+1;mid=0;
    t[p].l=l;t[p].r=r;//保存区间端点
    if(l==r){
        t[p].sum=a[l];
        return ;
    }
    mid=(t[p].l+t[p].r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[p].sum=t[ls].sum+t[rs].sum;//维护sum
}
void spread(int p){
    int ls,rs,lsn,rsn;
    ls=p*2;rs=p*2+1;lsn=t[ls].r-t[ls].l+1;rsn=t[rs].r-t[rs].l+1;
    if(t[p].lazy){//有懒惰标
        t[ls].sum+=t[p].lazy*lsn;//lsn:左儿区间长，rsn类似
        t[rs].sum+=t[p].lazy*rsn;
        t[ls].lazy+=t[p].lazy;//下传
        t[rs].lazy+=t[p].lazy;
        t[p].lazy=0;//清空
    }
}
void change(int p,int fl,int fr,int add){//区间加
    int ls,rs,mid,n;
    ls=p*2;rs=p*2+1;mid=0;n=t[p].r-t[p].l+1;
    if(t[p].l>=fl&&t[p].r<=fr){//如果区间完全包含直接加，同时标记懒惰
        t[p].sum+=add*n;
        t[p].lazy+=add;
        return ;
    }
    spread(p);//要继续递归，先下传标记
    mid=(t[p].l+t[p].r)>>1;
    if(fl<=mid) change(ls,fl,fr,add);
    if(fr>mid) change(rs,fl,fr,add);
    t[p].sum=t[ls].sum+t[rs].sum;
}
int query(int p,int fl,int fr){
    int ls,rs,mid,sum;
    ls=p*2;rs=p*2+1;mid=0;sum=0;
    if(t[p].l>=fl&&t[p].r<=fr) return t[p].sum;
    spread(p);
    mid=(t[p].l+t[p].r)>>1;
    sum=0;
    if(fl<=mid) sum+=query(ls,fl,fr);
    if(fr>mid) sum+=query(rs,fl,fr);
    return sum;//返回查询结果
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        cin>>opt;
        if(opt==1){
            cin>>l>>r>>x;
            change(1,l,r,x);
        }
        if(opt==2){
            cin>>l>>r;
            cout<<query(1,l,r)<<"\n";
        }
    }
    return 0;
}

by 紫玄月 @ 2024-03-03 16:25:49

@cj180202 感谢帮助，已关