平衡树 TLE70pts求调

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

const int N = 1e5 + 10;
int n, m, a[N], son[N][2], num[N], rd[N], sz[N], addv[N], sum[N], rt, v; 

int add(int w) {
    sz[++v] = 1;
    rd[v] = rand();
    num[v] = w;
    addv[v] = sum[v] = 0;
    return v;
}

void pushup(int x) {
    sz[x] = sz[son[x][0]] + sz[son[x][1]] + 1;
    sum[x] = sum[son[x][0]] + sum[son[x][1]] + num[x];
}

void pushdown(int x) {
    if(addv[x]) {
        sum[x] += addv[x] * sz[x];
        num[x] += addv[x];
        if(son[x][0])
            addv[son[x][0]] += addv[x];
        if(son[x][1])
            addv[son[x][1]] += addv[x];
        addv[x] = 0;
    }
}

int merge(int x, int y){
    if(!x or !y)
        return x | y;
    if(rd[x] < rd[y]) {
        pushdown(x);
        son[x][1] = merge(son[x][1], y);
        pushup(x);
        return x;
    }
    else {
        pushdown(y);
        son[y][0] = merge(x, son[y][0]);
        pushup(y);
        return y;
    }
}

void split(int x, int &y, int &z, int w){
    if(!x) {
        y = z = 0;
        return;
    }
    pushdown(x);
    int sum = sz[son[x][0]] + 1;
    if(sum <= w) {
        y = x;
        split(son[x][1], son[x][1], z, w - sum);
    }
    else {
        z = x;
        split(son[x][0], y, son[x][0], w);
    }
    pushup(x);
}

void dfs(int x) {
    if(!x)
        return;
    pushdown(x);
    dfs(son[x][0]);
    dfs(son[x][1]);
    pushup(x);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//  freopen(".in", "r+", stdin);
//  freopen(".out", "w+", stdout);

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        rt = merge(rt, add(a[i]));
    }
    while(m--) {
        int op;
        cin >> op;
        if(op == 1) {
            int l, r, x, y, z, k;
            cin >> l >> r >> k;
            split(rt, x, z, r);
            split(x, x, y, l - 1);
            addv[y] += k;
            rt = merge(merge(x, y), z);
        }
        else {
            int l, r, x, y, z;
            cin >> l >> r;
            split(rt, x, z, r);
            split(x, x, y, l - 1);
            dfs(y);
            cout << sum[y] << endl;
            rt = merge(merge(x, y), z);
        }
    }
//  dfs(rt);

    return 0;
}