9RE1WA求调

代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
int num[100005];
int tree[4000005];
int tag[4000005];
int n,m;

void push_up(int p){
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
}

void build(int l,int r,int x,int a[]){
    if(l == r){
        tree[x] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l,mid,x * 2,a);
    build(mid + 1,r,x * 2 + 1,a);
    tree[x] = tree[x * 2] + tree[x * 2 + 1];
}

int addtag(int p,int l,int r,int value){ //给编号为p的区间[l,r]打tag 
    tag[p] += value;
    tree[p] += value * (r - l + 1);
}

void push_down(int p,int pl,int pr){ //将tag传给子树 
    if(tag[p]){ //如果以前有tag 
        int mid = (pl + pr) / 2;
        addtag(p * 2,pl,mid,tag[p]);
        addtag(p * 2 + 1,mid + 1,pr,tag[p]);
        tag[p] = 0;
    }
}

void update(int l, int r,int p,int pl,int pr,int value){ //区间修改[pl,pr]内元素加value
    if(l >= pl && r <= pr){ //完全覆盖时直接返回 
        addtag(p,l,r,value);
        return;
    }
    push_down(p,l,r); //不能覆盖时，把tag向下传递并计算 
    int mid = (l + r) / 2;
    if(pl <= mid) update(l,mid,p * 2,pl,pr,value);
    if(pr > mid) update(mid + 1,r,p * 2 + 1,pl,pr,value);
    push_up(p);
}

int query(int l,int r,int p,int pl,int pr){ //查询区间[pl,pr]；p是当前区间在线段树的编号 
    if(r <= pr && l >= pl){
        return tree[p];
    }
    push_down(p,l,r);
    int res = 0;
    int mid = (l + r) / 2;
    if(pl <= mid) res += query(l,mid,p * 2, pl,pr);
    if(pr > mid) res += query(mid + 1,r,p * 2 + 1,pl,pr);
    return res; 
}

signed main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> num[i];
    } 
    build(1,n,1,num);
    for(int i = 1; i <= m;i++){
        int op;
        cin >> op;
        if(op == 1){
            int value,x,y;
            cin >> x >> y >> value;
            update(1,n,1,x,y,value);
        }else{
            int x,y;
            cin >> x >> y;
            cout << query(1,n,1,x,y) << endl;
        } 
    }
    return 0;
}