0分求调【哭ing】

lonely_star @ 2024-07-25 13:51:36

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+2;
struct node{
    int l,r,sum,lz;
} tree[maxn*4];
int n,m;
int a[maxn];
void build(int i,int l,int r){
    tree[i].l=l;
    tree[i].r=r;
    if(l==r){
        tree[i].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}
void pushdown(int i){
    if(tree[i].lz==0)return;
    tree[i*2].lz+=tree[i].lz;
    tree[i*2+1].lz+=tree[i].lz;
    int mid=(tree[i*2].l+tree[i*2].r)/2;
    tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);
    tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
    tree[i].lz=0;
    return;
}
void add(int i,int l,int r,int k){
    if(tree[i].r<=r&&tree[i].l>=l){
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;
        return ;
    }
    pushdown(i);
    if(tree[i*2].r>=l)add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)add(i*2+1,l,r,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return;
}
int check(int i,int l,int r){
    if(tree[i].l>=l&&tree[i].r<=r){
        return tree[i].sum;
    }
    if(tree[i].l>r||tree[i].r<l)return 0;
    pushdown(i);
    int w=0;
    if(tree[i*2].r>=l)w+=check(i*2,l,r);
    if(tree[i*2+1].l<=r)w+=check(i*2+1,l,r);
    return w;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    int q,x,y,k;
    for(int i=1;i<=m;i++){
        cin>>q;
        cin>>x>>y;
        if(q==1){
            cin>>k;
            add(1,x,y,k);
        }else{
            cout<<check(1,x,y)<<"\n";
        }
    }
    return 0;
}

by Lizhuohang0501 @ 2024-07-25 14:34:43

已调好

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+2;
struct node{
    int l,r;long long sum,lz;
    //不开long long见祖宗 
} tree[maxn*4];
int n,m;
int a[maxn];
void build(int i,int l,int r){
    tree[i].l=l;
    tree[i].r=r;
    if(l==r){
        tree[i].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}
void pushdown(int i){
    if(tree[i].lz==0)return;
    tree[i*2].lz+=tree[i].lz;
    tree[i*2+1].lz+=tree[i].lz;
    int mid=(tree[i].l+tree[i].r)/2;//i*2变为i，mid为当前区间的值 
    tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);
    tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
    tree[i].lz=0;
    return;
}
void add(int i,int l,int r,int k){
    if(tree[i].r<=r&&tree[i].l>=l){
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;
        return ;
    }
    pushdown(i);
    int mid = (tree[i].l + tree[i].r) / 2;//先计算mid
    if(l<=mid)add(i*2,l,r,k);//用mid进行判断 
    if(r>mid)add(i*2+1,l,r,k);//同上 
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return;
}
long long check(int i,int l,int r){//不开long long见祖宗 
    if(tree[i].l>=l&&tree[i].r<=r){
        return tree[i].sum;
    }
    if(tree[i].l>r||tree[i].r<l)return 0;
    pushdown(i);
    long long w=0;//不开long long见祖宗 
    int mid = (tree[i].l + tree[i].r) / 2;//先计算mid
    if(mid>=l)w+=check(i*2,l,r);//用mid进行判断 
    if(mid<r)w+=check(i*2+1,l,r);//同上 
    return w;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    int q,x,y,k;
    for(int i=1;i<=m;i++){
        cin>>q;
        cin>>x>>y;
        if(q==1){
            cin>>k;
            add(1,x,y,k);
        }else{
            cout<<check(1,x,y)<<"\n";
        }
    }
    return 0;
}

by lonely_star @ 2024-07-25 14:40:54

@Lizhuohang0501 万分感谢（膜拜）