10tps求调

RikkaTakanashi @ 2023-09-24 20:13:26

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

#define int long long
#define ls id<<1
#define rs id<<1|1
const int maxn=1e5+5;
int n,m,a[maxn];

struct node{
    int l,r,num,lazy;
}t[maxn<<2];
void push(int id){
    t[id].num=t[ls].num+t[rs].num;
}
void down(int id){
    int l=t[id].l,r=t[id].r;
    int mid=(l+r)>>1;
    t[ls].lazy+=t[id].lazy;
    t[ls].num+=((mid-l+1))*t[id].lazy;
    t[rs].lazy+=t[id].lazy;
    t[rs].num+=((r-mid+2))*t[id].lazy;
    t[id].lazy=0;
}
void build(int l,int r,int id){
    t[id].l=l,t[id].r=r;
    if(l==r){
        t[id].num=a[l];
        return ;
    }
    int mid=t[id].l+((t[id].r-t[id].l)>>1);
    build(l,mid,ls);
    build(mid+1,r,rs);
    push(id);
    return ;
}
void update(int l,int r,int id,int z){
    //printf("l:%d r:%d nowl:%d nowr:%d id:%d\n",l,r,t[id].l,t[id].r,id);
    if(l<=t[id].l && r>=t[id].r){
        t[id].num+=(t[id].r-t[id].l+1)*z,t[id].lazy+=z;
        return ;
    }
    int mid=t[id].l+((t[id].r-t[id].l)>>1);
    down(id);
    if(l<=mid) update(l,r,ls,z);
    if(r>mid) update(l,r,rs,z);
    push(id);
}
int query(int l,int r,int id){
    //printf("l:%d r:%d nowl:%d nowr:%d id:%d\n",l,r,t[id].l,t[id].r,id);
    if(l<=t[id].l && r>=t[id].r) return t[id].num;
    if(t[id].lazy) down(id);
    int ret=0;
    int mid=t[id].l+((t[id].r-t[id].l)>>1);
    if(l<=mid) ret+=query(l,r,ls);
    if(r>mid) ret+=query(l,r,rs);
    return ret;
}
signed main(){
    cin >> n >> m; 
    for(int i=1;i<=n;i++) cin >> a[i];
    build(1,n,1);
    while(m--){
        int opt,x,y,z;
        cin >> opt >> x >> y;
        if(opt==1){
            cin >> z;
            update(x,y,1,z);
        }else{
            cout << query(x,y,1) << endl;
        }
    }
    return 0;
}

by TerryHan_Su @ 2023-09-24 20:29:23

t[rs].num+=((r-mid+2))*t[id].lazy;这里错了

代码：

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

#define int long long
#define ls id<<1
#define rs id<<1|1
const int maxn=1e5+5;
int n,m,a[maxn];

struct node{
    int l,r,num,lazy;
}t[maxn<<2];
void push(int id){
    t[id].num=t[ls].num+t[rs].num;
}
void down(int id){
    int l=t[id].l,r=t[id].r;
    int mid=(l+r)>>1;
    if(t[id].lazy!=0){
    t[ls].lazy+=t[id].lazy;
    t[ls].num+=((mid-l+1))*t[id].lazy;
    t[rs].lazy+=t[id].lazy;
    t[rs].num+=((r-mid))*t[id].lazy;
    t[id].lazy=0;
    }
}
void build(int l,int r,int id){
    t[id].l=l,t[id].r=r;
    if(l==r){
        t[id].num=a[l];
        return ;
    }
    int mid=t[id].l+((t[id].r-t[id].l)>>1);
    build(l,mid,ls);
    build(mid+1,r,rs);
    push(id);
    return ;
}
void update(int l,int r,int id,int z){
    if(l<=t[id].l && r>=t[id].r){
        t[id].num+=(t[id].r-t[id].l+1)*z,t[id].lazy+=z;
        return ;
    }
    int mid=t[id].l+((t[id].r-t[id].l)>>1);
    down(id);
    if(l<=mid) update(l,r,ls,z);
    if(r>mid) update(l,r,rs,z);
    push(id);
}
int query(int l,int r,int id){
    if(l<=t[id].l && r>=t[id].r) return t[id].num;
    if(t[id].lazy) down(id);
    int ret=0;
    int mid=t[id].l+((t[id].r-t[id].l)>>1);
    if(l<=mid) ret+=query(l,r,ls);
    if(r>mid) ret+=query(l,r,rs);
    return ret;
}
signed main(){
    cin >> n >> m; 
    for(int i=1;i<=n;i++) cin >> a[i];
    build(1,n,1);
    while(m--){
        int opt,x,y,z;
        cin >> opt >> x >> y;
        if(opt==1){
            cin >> z;
            update(x,y,1,z);
        }else{
            cout << query(x,y,1) << endl;
        }
    }
    return 0;
}

by Iwara @ 2023-09-24 20:30:44

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

#define int long long
#define ls id<<1
#define rs id<<1|1
const int maxn=1e5+5;
int n,m,a[maxn];

struct node{
    int l,r,num,lazy;
}t[maxn<<2];
void push(int id){
    t[id].num=t[ls].num+t[rs].num;
}
void down(int id){
    int l=t[id].l,r=t[id].r;
    int mid=(l+r)>>1;
    t[ls].lazy+=t[id].lazy;
    t[ls].num+=((mid-l+1))*t[id].lazy;
    t[rs].lazy+=t[id].lazy;
    t[rs].num+=((r-mid))*t[id].lazy;//这里
    t[id].lazy=0;
    return;
}
void build(int l,int r,int id){
    if(l>r)return;//这里
    t[id].l=l,t[id].r=r;
    if(l==r){
        t[id].num=a[l];
        return ;
    }
    int mid=(t[id].l+t[id].r)>>1;//这里
    build(l,mid,ls);
    build(mid+1,r,rs);
    push(id);
    return ;
}
void update(int l,int r,int id,int z){
    //printf("l:%d r:%d nowl:%d nowr:%d id:%d\n",l,r,t[id].l,t[id].r,id);
    if(l<=t[id].l && r>=t[id].r){
        t[id].num+=(t[id].r-t[id].l+1)*z,t[id].lazy+=z;
        return ;
    }
    int mid=(t[id].l+t[id].r)>>1;//这里
    down(id);
    if(l<=mid) update(l,r,ls,z);
    if(r>mid) update(l,r,rs,z);
    push(id);
    return;
}
int query(int l,int r,int id){
    //printf("l:%d r:%d nowl:%d nowr:%d id:%d\n",l,r,t[id].l,t[id].r,id);
    if(l<=t[id].l && r>=t[id].r) return t[id].num;
    if(t[id].lazy) down(id);
    int ret=0;
    int mid=(t[id].l+t[id].r)>>1;//这里
    if(l<=mid) ret+=query(l,r,ls);
    if(r>mid) ret+=query(l,r,rs);
    push(id);//这里
    return ret;
}
signed main(){
    cin >> n >> m; 
    for(int i=1;i<=n;i++) cin >> a[i];
    build(1,n,1);
    while(m--){
        int opt,x,y,z;
        cin >> opt >> x >> y;
        if(opt==1){
            cin >> z;
            update(x,y,1,z);
        }else{
            cout << query(x,y,1) << endl;
        }
    }
    return 0;
}

帮您改好了

by TerryHan_Su @ 2023-09-24 20:33:29

@TSH2

by RikkaTakanashi @ 2023-09-24 21:00:00

谢谢