該比賽已結束，您無法在比賽模式下遞交該題目。您可以點選“在題庫中開啟”以普通模式檢視和遞交本題。

Problem Description

Author: louishuang

有人想要耍毒寫了一顆線段樹結果寫爛了

再幫他除蟲一次吧!

修改 $\le 6$ 個字元且 AC： 100 分。

修改 $\le 25$ 個字元且 AC： 50 分。

否則：0 分。

#include <iostream>
#include <vector>

using namespace std;

#define int long long

const int MAXN = 200005;
int tree[MAXN * 4], lazy[MAXN * 4];

void push_down(int node, int l, int r) {
    if (lazy[node] != 0) {
        int mid = (l + r) / 2;
        tree[node * 2] += lazy[node] * (mid - l + 1);
        tree[node * 2 + 1] += lazy[node] * (r - mid);
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
        lazy[node] = 0;
    }
}

void update(int node, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        tree[node] += val * (r - l + 1);
        lazy[node] += val;
        return;
    }
    push_down(node, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) update(node * 2, l, mid, ql, qr, val);
    if (qr > mid) update(node * 2 + 1, mid + 1, r, ql, qr, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int query(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[node];
    push_down(node, l, r);
    int mid = (l + r) / 2;
    int res = 0;
    if (ql <= mid) res += query(node * 2, l, mid, ql, qr);
    if (qr > mid) res += query(node * 2 + 1, mid + 1, r, ql, qr);
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            int val;
            cin >> val;
            update(1, 1, n, l, r, val);
        } else {
            cout << query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

5 3
1 1 5 2
1 2 4 3
2 1 5

19