Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define F first
- #define S second
- #define all(x) (x).begin(), (x).end()
- #define fast cin.tie(0);cin.sync_with_stdio(0);cout.tie(0);cout.sync_with_stdio(0)
- #define file freopen("lca_rmq.in", "r", stdin); freopen("lca_rmq.out", "w", stdout)
- typedef long long ll;
- typedef long double ld;
- using namespace std;
- struct nd {
- int vl, ad;
- };
- nd t[888888];
- int a[222222];
- void push(int v, int l, int r) {
- t[v].vl += t[v].ad * max(0, r - l + 1);
- t[v * 2].ad += t[v].ad;
- t[v * 2 + 1].ad += t[v].ad;
- t[v].ad = 0;
- }
- void upd(int v, int tl, int tr, int l, int r, ll add) {
- push(v, tl, tr);
- if (l > r) return;
- if (tl == l && tr == r) {
- t[v].ad += add;
- push(v, tl, tr);
- }
- else {
- push(v, tl, tr);
- int tm = (tl + tr) / 2;
- upd(v * 2, tl, tm, l, min(r, tm), add);
- upd(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, add);
- t[v].vl = t[v * 2].vl + t[v * 2 + 1].vl;
- }
- }
- ll get_sum(int v, int tl, int tr, int l, int r) {
- if (l > r) return 0;
- push(v, tl, tr);
- if (tl == l && tr == r) return t[v].vl;
- int tm = (tl + tr) / 2;
- return get_sum(v * 2, tl, tm, l, min(r, tm)) +
- get_sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
- }
- signed main() {
- fast;
- int n, m;
- cin >> n >> m;
- while (m--) {
- int uu;
- cin >> uu;
- if (uu == 1) {
- int l, r, s;
- cin >> l >> r >> s;
- upd(1, 0, n - 1, l, r - 1, s);
- }
- else {
- int l, r;
- cin >> l >> r;
- cout << get_sum(1, 0, n - 1, l, r - 1) << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement