Segment Tree Beats · Thuật toán Canuc80k

Có những cập nhật đoạn không viết được thành nhãn lười: lấy căn, lấy dư, hay $a_i \leftarrow \min(a_i, x)$ tác động khác nhau lên từng phần tử. Segment tree beats vẫn dùng cây phân đoạn, nhưng cho phép đệ quy sâu hơn mức cần thiết, và chứng minh bằng phân tích khấu hao rằng tổng số nút bị thăm thêm là nhỏ. Hai mẫu chính: dừng sớm khi phép đổi chắc chắn không tác dụng (căn, lấy dư), và giữ cực đại thứ hai để khi chỉ nhóm cực đại bị hạ thì xử lý cả nút như một nhãn lười.

Căn bậc hai: mỗi phần tử chỉ đổi vài lần

Lấy căn nguyên một số tới $10^{18}$ sáu lần là về $1$ ; sau đó căn không đổi giá trị nữa. Cây giữ tổng và cực đại của mỗi nút. Cập nhật đoạn đi xuống tới tận lá như cập nhật điểm, nhưng bỏ qua mọi nút có cực đại không quá 1. Mỗi phần tử bị chạm lá tối đa 6 lần, mỗi lần tốn $O(\log n)$ , nên tổng $O(6 n \log n)$ cộng chi phí đi qua các nút bị bỏ qua, $O(\log n)$ mỗi truy vấn.

Căn của số tới $10^{18}$ tính bằng sqrtl rồi chỉnh lại $\pm 1$ cho chắc, vì số thực có thể lệch ở gần số chính phương.

Bấm Lấy căn vài lần: các nút toàn số 1 (xanh lá) bị bỏ qua, chỉ lá còn đổi được mới bị chạm.

Ví dụCăn Bậc Hai Theo Đoạn

Đề. Nhiều bộ tới hết tệp; mỗi bộ $N, M \le 10^5$ , phần tử tới $10^{18}$ . Thao tác 0 lấy căn nguyên mọi phần tử trên đoạn, thao tác 1 hỏi tổng đoạn (đoạn có thể cho ngược đầu). In Case #k: và một dòng trống sau mỗi bộ.

Lời giải. Cây phân đoạn giữ tổng và cực đại của mỗi đoạn. Lấy căn không có nhãn lười, vì căn của một tổng không tính được từ tổng; ta đi xuống tận từng lá cần đổi. Điều làm cách “thô” này đủ nhanh là nút có cực đại không quá 1 được bỏ qua cả cụm. Đề cho đoạn có thể ngược đầu, nên đổi chỗ $X, Y$ khi $X > Y$ .

Bước 1: căn nguyên chính xác. sqrtl trên số tới $10^{18}$ có thể lệch một đơn vị ở gần số chính phương. Vòng đầu kéo r xuống cho tới khi $r^2 \le x$ , vòng sau đẩy lên khi $(r + 1)^2 \le x$ .

C++

ll isqrt(ll x) {
    ll r = sqrtl((long double)x);
    while (r * r > x) r--;
    while ((r + 1) * (r + 1) <= x) r++;
    return r;
}

Bước 2: cập nhật đi xuống tận lá. Dòng đầu gộp hai lý do dừng: nút ngoài đoạn, hoặc mx[x] <= 1 thì mọi phần tử trong nút là 0 hoặc 1, căn không đổi gì. Còn lại thì đi xuống; tới lá thì lấy căn, trên đường về tính lại sum và mx.

C++

void update(int x, int l, int r, int ql, int qr) {
    if (qr < l || r < ql || mx[x] <= 1) return;
    if (l == r) {
        sum[x] = mx[x] = isqrt(sum[x]);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * x, l, mid, ql, qr);
    update(2 * x + 1, mid + 1, r, ql, qr);
    sum[x] = sum[2 * x] + sum[2 * x + 1];
    mx[x] = max(mx[2 * x], mx[2 * x + 1]);
}

get là tổng đoạn thường, không có nhãn nào cần đẩy. while (cin >> n) đọc tới hết tệp; mỗi bộ gọi build lại.

Vì sao đủ nhanh: mỗi phần tử tới $10^{18}$ chỉ bị chạm lá tối đa 6 lần trước khi về 1, mỗi lần một đường $O(\log n)$ . Phần còn lại của một lần cập nhật là các nút bị bỏ qua hoặc nằm ngoài đoạn, cũng $O(\log n)$ .

Code đầy đủ

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

const int N = 1e5 + 5;
int n, m;
ll a[N], sum[4 * N], mx[4 * N];

ll isqrt(ll x) {
    ll r = sqrtl((long double)x);
    while (r * r > x) r--;
    while ((r + 1) * (r + 1) <= x) r++;
    return r;
}

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

void update(int x, int l, int r, int ql, int qr) {
    if (qr < l || r < ql || mx[x] <= 1) return;
    if (l == r) {
        sum[x] = mx[x] = isqrt(sum[x]);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * x, l, mid, ql, qr);
    update(2 * x + 1, mid + 1, r, ql, qr);
    sum[x] = sum[2 * x] + sum[2 * x + 1];
    mx[x] = max(mx[2 * x], mx[2 * x + 1]);
}

ll get(int x, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[x];
    int mid = (l + r) / 2;
    return get(2 * x, l, mid, ql, qr) + get(2 * x + 1, mid + 1, r, ql, qr);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int tc = 0;
    while (cin >> n) {
        for (int i = 1; i <= n; i++) cin >> a[i];
        build(1, 1, n);
        cin >> m;
        cout << "Case #" << ++tc << ":\n";
        while (m--) {
            int t, x, y;
            cin >> t >> x >> y;
            if (x > y) swap(x, y);
            if (t == 0) update(1, 1, n, x, y);
            else cout << get(1, 1, n, x, y) << '\n';
        }
        cout << '\n';
    }
}

OutputCase #1:
42
10
5
2

Tổng $O((6n + m) \log n)$ .

Lấy dư: thế năng là logarit của giá trị

$a \bmod x$ với $x \le a$ cho kết quả nhỏ hơn $a/2$ : nếu $x \le a/2$ thì dư nhỏ hơn $x$ , ngược lại dư là $a - x < a/2$ . Vậy mỗi lần một phần tử thật sự đổi, giá trị của nó giảm ít nhất một nửa. Bỏ qua nút có cực đại nhỏ hơn $x$ , đi xuống lá ở mọi nút còn lại. Tổng số lần một phần tử đổi là $O(\log V)$ , mỗi lần $O(\log n)$ .

Gán điểm $a_k = x$ làm tăng thế năng của đúng một phần tử thêm $O(\log V)$ , nên tổng vẫn là $O((n + q) \log n \log V)$ . Lập luận “thế năng” này là cách kiểm một phép đoạn bất kỳ có dùng được kỹ thuật dừng sớm hay không.

Nút có cực đại nhỏ hơn x bị bỏ qua; mỗi lá bị chạm thì giá trị giảm ít nhất một nửa.

Hỏi nhanh

Phần tử $10^9$ bị lấy dư liên tục bởi các $x$ khác nhau, mỗi lần đều làm nó đổi. Nó đổi được nhiều nhất khoảng bao nhiêu lần?

Ví dụPhần Dư Trên Dãy

Đề. Dãy $n \le 10^5$ số tới $10^9$ , $m \le 10^5$ thao tác: tổng đoạn, lấy dư cả đoạn cho $x$ , gán một phần tử.

Lời giải. Cùng khung với ví dụ trước: cây giữ tổng và cực đại, lấy dư đi xuống tận lá. Nút có cực đại nhỏ hơn $x$ thì mọi phần tử trong đó đã nhỏ hơn $x$ , lấy dư không đổi gì, bỏ qua. Lệnh gán một phần tử là cập nhật điểm bình thường.

Bước 1: lấy dư cả đoạn. pull tính lại tổng và cực đại từ hai con; mọi hàm sửa cây gọi nó trên đường về.

C++

void modAll(int x, int l, int r, int ql, int qr, ll v) {
    if (qr < l || r < ql || mx[x] < v) return;
    if (l == r) {
        sum[x] = mx[x] = sum[x] % v;
        return;
    }
    int mid = (l + r) / 2;
    modAll(2 * x, l, mid, ql, qr, v);
    modAll(2 * x + 1, mid + 1, r, ql, qr, v);
    pull(x);
}

Bước 2: gán một phần tử. Đi một đường từ gốc tới lá p, gán rồi pull ngược lên. Ba loại thao tác có số tham số khác nhau, nên mỗi nhánh trong main tự đọc phần của mình.

Vì sao đủ nhanh: mỗi lần một lá thật sự đổi, giá trị của nó giảm ít nhất một nửa ( $a \bmod x < a/2$ khi $x \le a$ ), nên một số tới $10^9$ đổi không quá khoảng 30 lần. Một lệnh gán đặt lại giá trị lớn cho đúng một phần tử, tức thêm khoảng 30 lần đổi nữa.

Code đầy đủ

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

const int N = 1e5 + 5;
int n, m;
ll a[N], sum[4 * N], mx[4 * N];

void pull(int x) {
    sum[x] = sum[2 * x] + sum[2 * x + 1];
    mx[x] = max(mx[2 * x], mx[2 * x + 1]);
}

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

void modAll(int x, int l, int r, int ql, int qr, ll v) {
    if (qr < l || r < ql || mx[x] < v) return;
    if (l == r) {
        sum[x] = mx[x] = sum[x] % v;
        return;
    }
    int mid = (l + r) / 2;
    modAll(2 * x, l, mid, ql, qr, v);
    modAll(2 * x + 1, mid + 1, r, ql, qr, v);
    pull(x);
}

void assign(int x, int l, int r, int p, ll v) {
    if (l == r) {
        sum[x] = mx[x] = v;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) assign(2 * x, l, mid, p, v);
    else assign(2 * x + 1, mid + 1, r, p, v);
    pull(x);
}

ll get(int x, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[x];
    int mid = (l + r) / 2;
    return get(2 * x, l, mid, ql, qr) + get(2 * x + 1, mid + 1, r, ql, qr);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            cout << get(1, 1, n, l, r) << '\n';
        } else if (t == 2) {
            int l, r;
            ll x;
            cin >> l >> r >> x;
            modAll(1, 1, n, l, r, x);
        } else {
            int k;
            ll x;
            cin >> k >> x;
            assign(1, 1, n, k, x);
        }
    }
}

Output34
22
16

Tổng số lần chạm lá $O((n + m) \log V)$ , mỗi lần $O(\log n)$ .

Hạ trần bằng cực đại thứ hai

Cập nhật $a_i \leftarrow \min(a_i, x)$ trên đoạn. Mỗi nút giữ cực đại mx, cực đại thứ hai nghiêm ngặt se, số lần cnt của cực đại, và tổng. Tại một nút nằm trọn trong đoạn:

$x \ge mx$ : không gì đổi, dừng.
$se < x < mx$ : chỉ các phần tử bằng $mx$ bị hạ xuống $x$ , nên tổng giảm $(mx - x) \cdot cnt$ , mx thành $x$ . Xử lý như một nhãn lười, dừng.
$x \le se$ : đi xuống hai con.

Nhãn đẩy xuống chính là mx của nút cha: con nào có cực đại lớn hơn thì bị hạ. Chứng minh khấu hao: mỗi lần đi xuống ở trường hợp ba, số giá trị phân biệt trong nút giảm ít nhất 1 (cả mx và se thành $x$ ), tổng $O((n + q) \log n)$ .

Mỗi nút ghi mx | se và số lần của mx. Cam: hạ nhóm cực đại rồi dừng; xanh dương: phải đi xuống; xanh lá: không đổi.

Ví dụHạ Trần

Đề. Dãy $n \le 10^6$ số dưới $2^{31}$ , $m \le 10^6$ thao tác: hạ trần $\min(a_i, x)$ trên đoạn, cực đại đoạn, tổng đoạn.

Lời giải. Mỗi nút giữ tổng, cực đại mx, cực đại thứ hai nghiêm ngặt se và số lần cnt của cực đại. Hạ trần về $x$ có ba trường hợp: $x \ge mx$ thì không đổi gì; $se < x < mx$ thì chỉ nhóm cực đại bị đổi, xử lý ngay tại nút; $x \le se$ thì đi xuống.

Bước 1: gộp hai con. Hai con cùng cực đại: số lần cộng lại, se là max hai se. Một bên lớn hơn: cực đại và số lần lấy từ bên ấy, còn cực đại của bên kia trở thành ứng viên cho se.

C++

void pull(int x) {
    int l = 2 * x, r = 2 * x + 1;
    sum[x] = sum[l] + sum[r];
    if (mx[l] == mx[r]) mx[x] = mx[l], cnt[x] = cnt[l] + cnt[r], se[x] = max(se[l], se[r]);
    else if (mx[l] > mx[r]) mx[x] = mx[l], cnt[x] = cnt[l], se[x] = max(se[l], mx[r]);
    else mx[x] = mx[r], cnt[x] = cnt[r], se[x] = max(mx[l], se[r]);
}

Bước 2: hạ nhóm cực đại. Chỉ đúng khi $v > se$ : tổng giảm đúng (mx - v) * cnt, còn se, cnt giữ nguyên.

C++

void lower(int x, int v) {
    if (v >= mx[x]) return;
    sum[x] -= (ll)(mx[x] - v) * cnt[x];
    mx[x] = v;
}

Bước 3: nhãn chính là mx của cha. Không cần biến nhãn riêng: con nào có cực đại lớn hơn mx của cha thì bị hạ xuống bằng nó; con không lớn hơn thì lower không làm gì.

C++

void push(int x) {
    lower(2 * x, mx[x]);
    lower(2 * x + 1, mx[x]);
}

Bước 4: hạ trần đoạn. Dừng khi ngoài đoạn hoặc mx[x] <= v; nằm trọn trong đoạn và se[x] < v thì lower rồi dừng; còn lại đẩy nhãn, đi xuống, pull. Lá đặt se = -1, nhỏ hơn mọi giá trị, nên ở lá điều kiện se < v luôn đúng. getMax, getSum cũng phải push trước khi xuống con.

C++

void chmin(int x, int l, int r, int ql, int qr, int v) {
    if (qr < l || r < ql || mx[x] <= v) return;
    if (ql <= l && r <= qr && se[x] < v) {
        lower(x, v);
        return;
    }
    push(x);
    int mid = (l + r) / 2;
    chmin(2 * x, l, mid, ql, qr, v);
    chmin(2 * x + 1, mid + 1, r, ql, qr, v);
    pull(x);
}

Vì sao đủ nhanh: chỉ trường hợp $v \le se$ làm cây đi sâu thêm, và mỗi lần như vậy cả mx lẫn se của nút trở thành $v$ , nên số giá trị phân biệt trong nút giảm ít nhất 1.

Code đầy đủ

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

const int N = 1e6 + 5;
int n, m, a[N], mx[4 * N], se[4 * N], cnt[4 * N];
ll sum[4 * N];

void pull(int x) {
    int l = 2 * x, r = 2 * x + 1;
    sum[x] = sum[l] + sum[r];
    if (mx[l] == mx[r]) mx[x] = mx[l], cnt[x] = cnt[l] + cnt[r], se[x] = max(se[l], se[r]);
    else if (mx[l] > mx[r]) mx[x] = mx[l], cnt[x] = cnt[l], se[x] = max(se[l], mx[r]);
    else mx[x] = mx[r], cnt[x] = cnt[r], se[x] = max(mx[l], se[r]);
}

void lower(int x, int v) {
    if (v >= mx[x]) return;
    sum[x] -= (ll)(mx[x] - v) * cnt[x];
    mx[x] = v;
}

void push(int x) {
    lower(2 * x, mx[x]);
    lower(2 * x + 1, mx[x]);
}

void build(int x, int l, int r) {
    if (l == r) {
        mx[x] = sum[x] = a[l], se[x] = -1, cnt[x] = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);
    pull(x);
}

void chmin(int x, int l, int r, int ql, int qr, int v) {
    if (qr < l || r < ql || mx[x] <= v) return;
    if (ql <= l && r <= qr && se[x] < v) {
        lower(x, v);
        return;
    }
    push(x);
    int mid = (l + r) / 2;
    chmin(2 * x, l, mid, ql, qr, v);
    chmin(2 * x + 1, mid + 1, r, ql, qr, v);
    pull(x);
}

int getMax(int x, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return -1;
    if (ql <= l && r <= qr) return mx[x];
    push(x);
    int mid = (l + r) / 2;
    return max(getMax(2 * x, l, mid, ql, qr), getMax(2 * x + 1, mid + 1, r, ql, qr));
}

ll getSum(int x, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[x];
    push(x);
    int mid = (l + r) / 2;
    return getSum(2 * x, l, mid, ql, qr) + getSum(2 * x + 1, mid + 1, r, ql, qr);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    cin >> m;
    while (m--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            int v;
            cin >> v;
            chmin(1, 1, n, l, r, v);
        } else if (t == 2) cout << getMax(1, 1, n, l, r) << '\n';
        else cout << getSum(1, 1, n, l, r) << '\n';
    }
}

Output9
31
25
5

Đếm khấu hao trên tổng số giá trị phân biệt của mọi nút: $O((n + m) \log n)$ .

Kẹp hai phía và cộng đoạn

Thêm nâng sàn $\max(a_i, x)$ và cộng đoạn: mỗi nút giữ đối xứng cực tiểu, cực tiểu thứ hai, số lần cực tiểu, và một nhãn cộng. Hạ trần chỉ đổi nhóm cực đại, nâng sàn chỉ đổi nhóm cực tiểu; phần khó là khi nút chỉ có một hay hai giá trị phân biệt, nhóm cực đại và nhóm cực tiểu trùng nhau một phần, nên khi hạ cực đại phải sửa cả cực tiểu (hoặc cực tiểu thứ hai) nếu chúng bằng cực đại cũ, và ngược lại.

Thứ tự đẩy nhãn xuống con: cộng trước, rồi hạ trần theo mx của cha, rồi nâng sàn theo mn của cha. Độ phức tạp khấu hao $O((n + q) \log^2 n)$ khi có cộng đoạn, đủ nhanh cho $2 \cdot 10^5$ .

Hỏi nhanh

Một nút chứa các giá trị $\{3, 3, 8\}$ . Hạ trần với $x = 5$ . Sau cập nhật, cực tiểu, cực đại của nút là bao nhiêu?

Ví dụKẹp Hai Phía

Đề. Dãy $n \le 2 \cdot 10^5$ số trong $[-10^{12}, 10^{12}]$ , $q \le 2 \cdot 10^5$ thao tác trên đoạn nửa mở $[l, r)$ : hạ trần, nâng sàn, cộng, tổng.

Lời giải. Mỗi nút giữ cả hai phía: cực đại, cực đại thứ hai, số lần cực đại; cực tiểu, cực tiểu thứ hai, số lần cực tiểu; thêm tổng, độ dài đoạn và nhãn cộng. Hạ trần chỉ đụng nhóm cực đại, nâng sàn chỉ đụng nhóm cực tiểu, cộng đoạn dời mọi giá trị. pull gồm hai khối giống hệt ví dụ trước, một cho phía cực đại, một cho phía cực tiểu (đổi > thành <, max thành min).

Bước 1: cộng cả nút. Tổng tăng v * len, mọi cực trị dời theo, trừ giá trị canh -INF, INF của mx2, mn2 (nghĩa là “không có”), vì dời chúng sẽ làm hỏng phép so sánh.

C++

void addNode(int x, ll v) {
    sum[x] += v * len[x];
    mx1[x] += v, mn1[x] += v, lz[x] += v;
    if (mx2[x] != -INF) mx2[x] += v;
    if (mn2[x] != INF) mn2[x] += v;
}

Bước 2: hạ trần kéo theo phía cực tiểu. Nút chỉ có một giá trị thì cực tiểu chính là cực đại cũ, phải hạ theo. Nút có hai giá trị thì cực tiểu thứ hai chính là cực đại cũ, cũng phải hạ theo. lift làm đối xứng cho nâng sàn.

C++

void lower(int x, ll v) {
    if (v >= mx1[x]) return;
    sum[x] -= (mx1[x] - v) * cmx[x];
    if (mn1[x] == mx1[x]) mn1[x] = v;
    else if (mn2[x] == mx1[x]) mn2[x] = v;
    mx1[x] = v;
}

Bước 3: thứ tự đẩy nhãn. Cộng trước, rồi hạ trần theo mx1 của cha, rồi nâng sàn theo mn1 của cha. mx1, mn1 của cha đã tính cả phần cộng, nên phải cộng cho con trước rồi mới so.

C++

void push(int x) {
    for (int c = 2 * x; c <= 2 * x + 1; c++) {
        if (lz[x]) addNode(c, lz[x]);
        lower(c, mx1[x]);
        lift(c, mn1[x]);
    }
    lz[x] = 0;
}

Bước 4: các thao tác. chmin, chmax, add, get cùng một khuôn như ví dụ trước. Chỉ số từ 0, đoạn $[l, r)$ đổi thành $[l, r - 1]$ bằng r--; thao tác 3 không có tham số thứ tư nên continue trước khi đọc b.

Giá trị tới $10^{12}$ cộng dồn qua nhiều lần cộng vẫn nằm xa $\pm 2 \cdot 10^{18}$ , nên INF = 2e18 không bị chạm tới và tổng vừa long long.

Code đầy đủ

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

const int N = 2e5 + 5;
const ll INF = 2e18;
int n, q, len[4 * N], cmx[4 * N], cmn[4 * N];
ll a[N], sum[4 * N], mx1[4 * N], mx2[4 * N], mn1[4 * N], mn2[4 * N], lz[4 * N];

void pull(int x) {
    int l = 2 * x, r = 2 * x + 1;
    sum[x] = sum[l] + sum[r];
    if (mx1[l] == mx1[r]) mx1[x] = mx1[l], cmx[x] = cmx[l] + cmx[r], mx2[x] = max(mx2[l], mx2[r]);
    else if (mx1[l] > mx1[r]) mx1[x] = mx1[l], cmx[x] = cmx[l], mx2[x] = max(mx2[l], mx1[r]);
    else mx1[x] = mx1[r], cmx[x] = cmx[r], mx2[x] = max(mx1[l], mx2[r]);
    if (mn1[l] == mn1[r]) mn1[x] = mn1[l], cmn[x] = cmn[l] + cmn[r], mn2[x] = min(mn2[l], mn2[r]);
    else if (mn1[l] < mn1[r]) mn1[x] = mn1[l], cmn[x] = cmn[l], mn2[x] = min(mn2[l], mn1[r]);
    else mn1[x] = mn1[r], cmn[x] = cmn[r], mn2[x] = min(mn1[l], mn2[r]);
}

void addNode(int x, ll v) {
    sum[x] += v * len[x];
    mx1[x] += v, mn1[x] += v, lz[x] += v;
    if (mx2[x] != -INF) mx2[x] += v;
    if (mn2[x] != INF) mn2[x] += v;
}

void lower(int x, ll v) {
    if (v >= mx1[x]) return;
    sum[x] -= (mx1[x] - v) * cmx[x];
    if (mn1[x] == mx1[x]) mn1[x] = v;
    else if (mn2[x] == mx1[x]) mn2[x] = v;
    mx1[x] = v;
}

void lift(int x, ll v) {
    if (v <= mn1[x]) return;
    sum[x] += (v - mn1[x]) * cmn[x];
    if (mx1[x] == mn1[x]) mx1[x] = v;
    else if (mx2[x] == mn1[x]) mx2[x] = v;
    mn1[x] = v;
}

void push(int x) {
    for (int c = 2 * x; c <= 2 * x + 1; c++) {
        if (lz[x]) addNode(c, lz[x]);
        lower(c, mx1[x]);
        lift(c, mn1[x]);
    }
    lz[x] = 0;
}

void build(int x, int l, int r) {
    len[x] = r - l + 1;
    if (l == r) {
        sum[x] = mx1[x] = mn1[x] = a[l];
        mx2[x] = -INF, mn2[x] = INF, cmx[x] = cmn[x] = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);
    pull(x);
}

void chmin(int x, int l, int r, int ql, int qr, ll v) {
    if (qr < l || r < ql || mx1[x] <= v) return;
    if (ql <= l && r <= qr && mx2[x] < v) {
        lower(x, v);
        return;
    }
    push(x);
    int mid = (l + r) / 2;
    chmin(2 * x, l, mid, ql, qr, v);
    chmin(2 * x + 1, mid + 1, r, ql, qr, v);
    pull(x);
}

void chmax(int x, int l, int r, int ql, int qr, ll v) {
    if (qr < l || r < ql || mn1[x] >= v) return;
    if (ql <= l && r <= qr && mn2[x] > v) {
        lift(x, v);
        return;
    }
    push(x);
    int mid = (l + r) / 2;
    chmax(2 * x, l, mid, ql, qr, v);
    chmax(2 * x + 1, mid + 1, r, ql, qr, v);
    pull(x);
}

void add(int x, int l, int r, int ql, int qr, ll v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        addNode(x, v);
        return;
    }
    push(x);
    int mid = (l + r) / 2;
    add(2 * x, l, mid, ql, qr, v);
    add(2 * x + 1, mid + 1, r, ql, qr, v);
    pull(x);
}

ll get(int x, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[x];
    push(x);
    int mid = (l + r) / 2;
    return get(2 * x, l, mid, ql, qr) + get(2 * x + 1, mid + 1, r, ql, qr);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    build(1, 0, n - 1);
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        r--;
        if (t == 3) {
            cout << get(1, 0, n - 1, l, r) << '\n';
            continue;
        }
        ll b;
        cin >> b;
        if (t == 0) chmin(1, 0, n - 1, l, r, b);
        else if (t == 1) chmax(1, 0, n - 1, l, r, b);
        else add(1, 0, n - 1, l, r, b);
    }
}

Output16
10
4

$O((n + q) \log^2 n)$ khi có cộng đoạn.

Khi đi thi

Phép đoạn làm giá trị “co lại” nhanh (căn, lấy dư, chia, AND, OR): giữ cực đại (hay cực tiểu, hay OR/AND của nút) để bỏ qua nút không đổi, đi xuống lá ở phần còn lại; chứng minh bằng thế năng.
Hạ trần, nâng sàn: giữ cực trị, cực trị thứ hai nghiêm ngặt và số lần; nhãn đẩy xuống là cực trị của cha.
Kết hợp cộng: đẩy theo thứ tự cộng, hạ trần, nâng sàn; cẩn thận nút chỉ có một hai giá trị phân biệt.

Tóm tắt

Dừng sớm: nút có cực đại không quá ngưỡng thì phép căn, lấy dư không đổi gì.
Lấy dư một số làm nó còn dưới một nửa, nên mỗi phần tử đổi $O(\log V)$ lần.
Hạ trần: $se < x < mx$ thì xử lý ở nút, giảm tổng $(mx - x) \cdot cnt$ ; ngược lại đi xuống.
Tổng chi phí chứng minh bằng khấu hao trên số giá trị phân biệt trong mỗi nút.

Bài tập

Đếm Ước Liên Tiếpcanuc80k6601Số ước của

x

về 2 sau vài lần (với

x \ge 3

); bỏ qua nút có cực đại không quá 2, sàng số ước trước.

LQDOJ

Dải Màu Tích Lũycanuc80k6605Nút có cả đoạn cùng màu thì tô lại xử lý ngay: cộng

|c - x|

cho cả đoạn bằng nhãn cộng lười; nút nhiều màu thì đi xuống.

LQDOJ

Ngưỡng Chiacanuc80k6606Mỗi vị trí giữ số lần cộng còn thiếu để

\lfloor a_i / b_i \rfloor

tăng; nút giữ cực tiểu của số này, về 0 thì đi xuống lá đặt lại.

LQDOJ

Cộng Và Lấy Căncanuc80k6607Cộng đoạn và lấy căn: khi cực đại và cực tiểu của nút có cùng độ giảm sau khi lấy căn, căn thành một phép cộng lười.

LQDOJ

Chia Sàn Trên Đoạncanuc80k6608Cộng và chia sàn: như bài căn, nút có cực đại trừ cực tiểu bằng độ chênh sau khi chia thì đổi thành cộng.

LQDOJ

Mặt Nạ Hai Chiềucanuc80k6609AND hay OR với

x

: nếu các bit bị đổi giống nhau ở mọi phần tử của nút (theo AND, OR của nút) thì phép biến thành cộng một hằng.

LQDOJ

Cộng, Chia Và Cực Đạicanuc80k6610Cộng, chia sàn và cực đại: giữ cực đại, cực tiểu, tổng; chia một nút khi cực đại và cực tiểu giảm cùng lượng thì dùng nhãn cộng.

LQDOJ

AND Và Cực Đạicanuc80k6611AND đoạn và cực đại: nút mà mọi phần tử có cùng các bit bị tắt thì AND là phép trừ hằng, ngược lại đi xuống.

LQDOJ

Vượt Mốc 42canuc80k6612Mỗi phần tử giữ khoảng cách tới lũy thừa 42 kế tiếp; nút giữ cực tiểu khoảng cách, âm thì đi xuống cập nhật lại.

LQDOJ

Khoảng Cách Hai Phíacanuc80k6613Hai cây hạ trần riêng cho phía trên và phía dưới; tổng chỉ tính ở vị trí đã có cả hai phía.

LQDOJ

Cực Đại Trong Lịch Sửcanuc80k6614Ngoài cực đại hiện tại, nhãn lười còn giữ lượng cộng lớn nhất từng đạt trên nhóm cực đại và nhóm còn lại để cập nhật cực đại lịch sử.

LQDOJ

Đọc thêm

Segment Tree BeatsUSACO GuideCài đặt và bài luyện.
区间最值操作 & 区间历史最值OI WikiHạ trần, cộng đoạn, cực đại lịch sử.