Sqrt Decomposition

Khối và hai loại đoạn

Chọn độ dài khối $B$, đánh số từ 1 và đặt id[i] = (i - 1) / B. Mỗi khối $k$ giữ một giá trị gộp, chẳng hạn tổng s[k]. Câu hỏi $[l, r]$ nằm trong một khối thì duyệt thẳng; ngược lại tách thành mảnh trái từ $l$ tới hết khối của $l$, các khối nguyên ở giữa, và mảnh phải từ đầu khối của $r$ tới $r$. Hai mảnh có không quá $2B$ phần tử, giữa có không quá $n / B$ khối, nên mỗi câu hỏi tốn $O(B + n / B)$. Tổng hai số hạng nhỏ nhất khi $B = \sqrt n$, còn $2\sqrt n$; với $n = 2 \cdot 10^5$ là khoảng 900 phép mỗi câu.

Gán $a_p = x$ chỉ làm đổi tổng một khối: s[id[p]] += x - a[p], $O(1)$. Tổng tiền tố không làm được việc này, Fenwick làm được nhanh hơn, nhưng khung khối là thứ dùng lại cho mọi mục sau.

Ví dụTổng Đoạn Linh Hoạt

Đề. Dãy $n \le 2 \cdot 10^5$ số, $q \le 2 \cdot 10^5$ thao tác: gán $a_p = x$, hoặc in tổng $a_l + \dots + a_r$.

Lời giải. Chia dãy thành các khối dài $B = \lfloor \sqrt n \rfloor$ và giữ tổng của mỗi khối. Một đoạn bất kỳ gồm tối đa hai mảnh biên lẻ và một dãy khối nằm trọn, mỗi phần tối đa $\sqrt n$ bước.

Bước 1: chia khối. id[i] = (i - 1) / B là khối của vị trí $i$; s[k] là tổng khối $k$, cộng dồn ngay khi đọc.

B = max(1LL, (ll)sqrt(n));
for (ll i = 1; i <= n; i++) {
    cin >> a[i];
    id[i] = (i - 1) / B;
    s[id[i]] += a[i];
}

Bước 2: tổng một đoạn. Cùng khối thì cộng thẳng. Khác khối thì ba phần: vòng đầu chạy từ $l$ tới hết khối của $l$, vòng giữa cộng tổng các khối nằm trọn, vòng cuối chạy lùi từ $r$ tới đầu khối của $r$.

ll get(ll l, ll r) {
    ll res = 0;
    if (id[l] == id[r]) {
        for (ll i = l; i <= r; i++) res += a[i];
        return res;
    }
    for (ll i = l; id[i] == id[l]; i++) res += a[i];
    for (ll k = id[l] + 1; k < id[r]; k++) res += s[k];
    for (ll i = r; id[i] == id[r]; i--) res += a[i];
    return res;
}

Bước 3: gán một phần tử. Sửa tổng khối bằng phần chênh y - a[x] rồi mới ghi giá trị mới, $O(1)$.

s[id[x]] += y - a[x];
a[x] = y;

Tổng có thể tới $2 \cdot 10^{14}$, phải dùng ll.

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

const ll N = 2e5 + 5;
ll n, q, B, a[N], id[N], s[N];

ll get(ll l, ll r) {
    ll res = 0;
    if (id[l] == id[r]) {
        for (ll i = l; i <= r; i++) res += a[i];
        return res;
    }
    for (ll i = l; id[i] == id[l]; i++) res += a[i];
    for (ll k = id[l] + 1; k < id[r]; k++) res += s[k];
    for (ll i = r; id[i] == id[r]; i--) res += a[i];
    return res;
}

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

    cin >> n >> q;
    B = max(1LL, (ll)sqrt(n));
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        id[i] = (i - 1) / B;
        s[id[i]] += a[i];
    }
    while (q--) {
        ll t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            s[id[x]] += y - a[x];
            a[x] = y;
        } else cout << get(x, y) << '\n';
    }
}

Input5 5
2 1 3 4 5
2 2 5
1 3 10
2 1 3
1 5 6
2 4 5

Output13
13
10

Gán $O(1)$, câu hỏi $O(\sqrt n)$.

Nhãn cho cả khối

Cập nhật trên đoạn dùng cùng cách tách. Khối nguyên chỉ ghi vào nhãn chung tag[k], nghĩa là “mọi phần tử của khối còn phải cộng thêm tag[k]”; phần tử ở hai mảnh biên sửa trực tiếp. Giá trị thật của $a_i$ là a[i] + tag[id[i]]. Mỗi cập nhật cũng $O(B + n / B)$. Nhãn có thể là phép cộng, phép gán, hay cặp (nhân, cộng) cho hàm bậc nhất $x \mapsto bx + c$; khi sửa lẻ một phần tử của khối đang mang nhãn không giao hoán với phép sửa, áp nhãn xuống cả khối trước.

Khối giữ dữ liệu đã sắp. Để đếm trên đoạn số phần tử nhỏ hơn $x$, mỗi khối giữ thêm một bản sao đã sắp các giá trị của nó. Cộng cả khối không đổi thứ tự trong khối, nên chỉ cần tăng nhãn; khối nguyên trả lời bằng một lần lower_bound với $x - \mathrm{tag}$. Mảnh biên bị sửa thì sắp lại khối đó, tốn $O(B \log B)$. Lúc này hai phía không còn cân: mảnh biên tốn $B \log B$, phần giữa tốn $(n / B) \log B$, vẫn cân ở $B = \sqrt n$; nhưng nếu mảnh biên tốn $B \log B$ còn phần giữa chỉ $n / B$ thì nên chọn $B = \sqrt{n / \log n}$. Ước lượng hai phía rồi chọn $B$ cho chúng bằng nhau.

Ví dụDấu Cộng Trên Đoạn

Đề. Dãy $n \le 5 \cdot 10^4$ số và $n$ thao tác: cộng $c$ vào mọi phần tử trên $[l, r]$, hoặc in giá trị hiện tại của $a_r$ (hai trường còn lại bị bỏ qua).

Lời giải. Đây là khung tối thiểu của nhãn khối; các bài sau chỉ thay nội dung của nhãn và của dữ liệu trong khối. tag[k] là lượng còn phải cộng cho mọi phần tử của khối $k$, nên giá trị thật của phần tử $i$ là a[i] + tag[id[i]].

Bước 1: cộng một đoạn. Mảnh biên sửa thẳng a[i]; khối nằm trọn chỉ tăng tag. Cùng khối thì chỉ có mảnh biên.

if (id[l] == id[r]) {
    for (ll i = l; i <= r; i++) a[i] += c;
    continue;
}
for (ll i = l; id[i] == id[l]; i++) a[i] += c;
for (ll k = id[l] + 1; k < id[r]; k++) tag[k] += c;
for (ll i = r; id[i] == id[r]; i--) a[i] += c;

Bước 2: hỏi một phần tử. Cộng nhãn của khối chứa nó.

cout << a[r] + tag[id[r]] << '\n';

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

const ll N = 5e4 + 5;
ll n, B, a[N], id[N], tag[N];

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

    cin >> n;
    B = max(1LL, (ll)sqrt(n));
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        id[i] = (i - 1) / B;
    }
    for (ll t = 1; t <= n; t++) {
        ll op, l, r, c;
        cin >> op >> l >> r >> c;
        if (op == 1) {
            cout << a[r] + tag[id[r]] << '\n';
            continue;
        }
        if (id[l] == id[r]) {
            for (ll i = l; i <= r; i++) a[i] += c;
            continue;
        }
        for (ll i = l; id[i] == id[l]; i++) a[i] += c;
        for (ll k = id[l] + 1; k < id[r]; k++) tag[k] += c;
        for (ll i = r; id[i] == id[r]; i--) a[i] += c;
    }
}

Input5
1 2 3 4 5
0 2 4 3
1 99 3 0
0 1 5 -2
1 -7 1 123
1 0 5 0

Output6
-1
3

Cộng đoạn $O(\sqrt n)$, hỏi $O(1)$.

Ví dụBao Nhiêu Số Bé Hơn

Đề. Dãy $n \le 5 \cdot 10^4$ số và $n$ thao tác: cộng $c$ vào đoạn $[l, r]$, hoặc đếm trên $[l, r]$ số phần tử nhỏ hơn hẳn $c^2$.

Lời giải. Mỗi khối giữ nhãn cộng tag[k] và vector v[k] các giá trị gốc của khối đã sắp (chưa cộng nhãn). Cộng vào cả khối không làm đổi thứ tự trong khối, nên chỉ tăng nhãn; chỉ mảnh biên mới làm thứ tự đổi và phải sắp lại. Phần tử của khối nằm trọn nhỏ hơn $w$ khi giá trị gốc nhỏ hơn $w - \mathrm{tag}$, đếm bằng một lần lower_bound. $c$ tới $2^{31}$ nên $c^2$ tới $2^{62}$, vẫn vừa ll.

Bước 1: dựng lại một khối. L[k], R[k] là vị trí đầu, cuối của khối; rebuild chép các giá trị gốc rồi sắp, $O(B \log B)$.

void rebuild(ll k) {
    v[k].clear();
    for (ll i = L[k]; i <= R[k]; i++) v[k].push_back(a[i]);
    sort(v[k].begin(), v[k].end());
}

Bước 2: mảnh biên. add chỉ được gọi cho một mảnh nằm trong một khối: sửa a[i] rồi dựng lại khối đó. calc đếm thẳng trên mảnh biên, so giá trị thật a[i] + tag với ngưỡng.

void add(ll l, ll r, ll c) {
    for (ll i = l; i <= r; i++) a[i] += c;
    rebuild(id[l]);
}

ll calc(ll l, ll r, ll x) {
    ll res = 0;
    for (ll i = l; i <= r; i++) res += (a[i] + tag[id[i]] < x);
    return res;
}

Bước 3: hai loại thao tác. Cộng: hai mảnh biên qua add, khối giữa tăng tag. Đếm: hai mảnh biên qua calc, khối giữa đếm bằng lower_bound trên v[k] với ngưỡng đã trừ nhãn.

for (ll k = id[x] + 1; k < id[y]; k++)
    res += lower_bound(v[k].begin(), v[k].end(), w - tag[k]) - v[k].begin();

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

const ll N = 5e4 + 5;
ll n, B, a[N], id[N], L[N], R[N], tag[N];
vector<ll> v[N];

void rebuild(ll k) {
    v[k].clear();
    for (ll i = L[k]; i <= R[k]; i++) v[k].push_back(a[i]);
    sort(v[k].begin(), v[k].end());
}

void add(ll l, ll r, ll c) {
    for (ll i = l; i <= r; i++) a[i] += c;
    rebuild(id[l]);
}

ll calc(ll l, ll r, ll x) {
    ll res = 0;
    for (ll i = l; i <= r; i++) res += (a[i] + tag[id[i]] < x);
    return res;
}

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

    cin >> n;
    B = max(1LL, (ll)sqrt(n));
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        id[i] = (i - 1) / B;
        R[id[i]] = i;
        if (!L[id[i]]) L[id[i]] = i;
    }
    for (ll k = 0; k <= id[n]; k++) rebuild(k);
    for (ll t = 1; t <= n; t++) {
        ll op, l, r, c;
        cin >> op >> l >> r >> c;
        ll x = l, y = r;
        if (op == 0) {
            if (id[x] == id[y]) add(x, y, c);
            else {
                add(x, R[id[x]], c);
                for (ll k = id[x] + 1; k < id[y]; k++) tag[k] += c;
                add(L[id[y]], y, c);
            }
            continue;
        }
        ll w = c * c, res;
        if (id[x] == id[y]) res = calc(x, y, w);
        else {
            res = calc(x, R[id[x]], w) + calc(L[id[y]], y, w);
            for (ll k = id[x] + 1; k < id[y]; k++)
                res += lower_bound(v[k].begin(), v[k].end(), w - tag[k]) - v[k].begin();
        }
        cout << res << '\n';
    }
}

Input5
1 4 2 8 3
1 1 5 2
0 2 4 -2
1 1 4 1
1 2 5 3
1 3 3 0

Output3
1
4
0

Mỗi thao tác $O(\sqrt n \log n)$: hai lần dựng lại khối hoặc $\sqrt n$ lần chặt nhị phân.

Ngưỡng theo tham số

Nhiều bài có một tham số $k$ trong mỗi câu hỏi (bước nhảy, modulo, kích thước tập) mà cách giải tốt phụ thuộc vào $k$ lớn hay nhỏ. Với $k > S$, đối tượng liên quan có ít phần tử, cỡ $n / k < n / S$, nên duyệt thẳng. Với $k \le S$ chỉ có $S$ giá trị khác nhau, nên tính sẵn một bảng cho từng giá trị, hoặc gom các câu hỏi cùng $k$ lại xử lý một lượt. Chọn $S = \sqrt n$ thì cả hai phía đều $O(\sqrt n)$ mỗi thao tác, hoặc $O(n \sqrt n)$ tổng cộng.

Ví dụTổng Theo Số Dư

Đề. Mảng $5 \cdot 10^5$ phần tử ban đầu bằng 0, $q \le 5 \cdot 10^5$ thao tác: cộng $y$ vào $a_x$, hoặc in tổng các $a_i$ với $i \bmod x = y$.

Lời giải. Chia câu hỏi theo modulo $x$ tại ngưỡng $S \approx \sqrt{5 \cdot 10^5} \approx 700$. Modulo nhỏ thì có ít, nên giữ sẵn đáp án cho mọi cặp $(d, r)$ với $d \le S$; modulo lớn thì dãy $y, y + x, \dots$ chỉ có ít số, cộng thẳng.

Bước 1: cộng vào $a_x$. Sửa $a_x$ và $S$ ô của bảng: với mỗi $d \le S$, phần tử $x$ thuộc nhóm dư x % d.

a[x] += y;
for (int d = 1; d <= S; d++) sm[d][x % d] += y;

Bước 2: câu hỏi. $x \le S$ thì đọc thẳng sm[x][y]; $x > S$ thì cộng các $a_i$ với $i = y, y + x, \dots$, không quá $5 \cdot 10^5 / 700 \approx 700$ số.

else if (x <= S) cout << sm[x][y] << '\n';
else {
    ll res = 0;
    for (ll i = y; i <= M; i += x) res += a[i];
    cout << res << '\n';
}

Biến vòng d, x, y khai báo int để phép chia lấy dư là phép 32 bit: chạy $3{,}5 \cdot 10^8$ lần, phép chia 64 bit chậm hơn hẳn.

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

const ll M = 5e5, S = 700;
ll q, a[M + 5], sm[S + 1][S + 1];

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

    cin >> q;
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            a[x] += y;
            for (int d = 1; d <= S; d++) sm[d][x % d] += y;
        } else if (x <= S) cout << sm[x][y] << '\n';
        else {
            ll res = 0;
            for (ll i = y; i <= M; i += x) res += a[i];
            cout << res << '\n';
        }
    }
}

Input7
1 3 5
1 8 4
1 10 -2
2 5 3
2 4 0
1 8 -1
2 2 0

Output9
4
1

Mỗi thao tác khoảng $S \approx 700$ phép.

Ví dụNhững Bước Nhảy Có Phí

Đề. Mảng cố định $a$ dài $n \le 10^5$ với $1 \le a_i \le n$. Mỗi câu hỏi $(p, k)$: khi $p \le n$ thì nhảy $p \gets p + a_p + k$; in số bước nhảy. Có $q \le 10^5$ câu hỏi.

Lời giải. Mỗi bước tiến ít nhất $k + 1$, nên $k > S$ thì mô phỏng không quá $n / S$ bước. Với $k \le S$, số bước từ $p$ là $\mathrm{dp}[p] = 1 + \mathrm{dp}[p + a_p + k]$, bằng 0 khi $p > n$, tính từ phải sang trong $O(n)$. Lưu bảng cho mọi $k \le S$ tốn $S \cdot n$ ô, quá nhiều; thay vào đó sắp câu hỏi theo $k$ và chỉ tính lại dp khi $k$ đổi.

Bước 1: sắp câu hỏi theo $k$. Giữ chỉ số gốc trong ord để cuối cùng in đáp án theo thứ tự đề.

for (ll i = 1; i <= q; i++) {
    cin >> P[i] >> K[i];
    ord[i] = i;
}
sort(ord + 1, ord + q + 1, cmp);

Bước 2: $k$ nhỏ, dùng chung một bảng. Khi $k$ đổi, tính lại dp[p] từ $p = n$ về 1; mỗi ô dựa vào ô nó nhảy tới, nằm bên phải nên đã tính. Có không quá $S$ giá trị $k$ khác nhau, mỗi lần $O(n)$.

if (k != last) {
    for (ll p = n; p >= 1; p--) {
        ll j = p + a[p] + k;
        dp[p] = 1 + (j <= n ? dp[j] : 0);
    }
    last = k;
}
ans[i] = dp[P[i]];

Bước 3: $k$ lớn, mô phỏng. Mỗi bước tiến hơn $S$, nên không quá $n / S$ bước.

ll p = P[i], cnt = 0;
while (p <= n) {
    p += a[p] + k;
    cnt++;
}
ans[i] = cnt;

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

const ll N = 1e5 + 5;
ll n, q, S, a[N], dp[N], P[N], K[N], ord[N], ans[N];

bool cmp(ll x, ll y) {
    return K[x] < K[y];
}

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

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    cin >> q;
    for (ll i = 1; i <= q; i++) {
        cin >> P[i] >> K[i];
        ord[i] = i;
    }
    sort(ord + 1, ord + q + 1, cmp);
    S = sqrt(n);
    ll last = 0;
    for (ll t = 1; t <= q; t++) {
        ll i = ord[t], k = K[i];
        if (k <= S) {
            if (k != last) {
                for (ll p = n; p >= 1; p--) {
                    ll j = p + a[p] + k;
                    dp[p] = 1 + (j <= n ? dp[j] : 0);
                }
                last = k;
            }
            ans[i] = dp[P[i]];
        } else {
            ll p = P[i], cnt = 0;
            while (p <= n) {
                p += a[p] + k;
                cnt++;
            }
            ans[i] = cnt;
        }
    }
    for (ll i = 1; i <= q; i++) cout << ans[i] << '\n';
}

Input5
1 2 1 3 1
4
1 1
2 2
1 3
4 1

Output3
1
2
1

Với $S = \sqrt n$, tổng $O((n + q)\sqrt n)$.

Nhảy ra khỏi khối

Mỗi ô $i$ chỉ sang một ô $i + a_i$ ở bên phải, và $a_i$ có thể bị sửa. Mô phỏng thẳng một đường nhảy tốn tới $n$ bước. Chia dãy thành khối và với mỗi ô lưu ba thứ: nxt[i] là ô đầu tiên ngoài khối của $i$ mà đường đi từ $i$ tới, cnt[i] là số bước để tới đó, lst[i] là ô cuối cùng trong khối trước khi rời. Chúng tính được từ phải sang trong khối: nếu $i + a_i$ còn trong khối thì kế thừa từ ô đó, ngược lại $i$ tự rời khối sau một bước.

Một câu hỏi đi theo nxt, mỗi bước qua ít nhất một khối, nên tốn $O(n / B)$. Sửa $a_p$ chỉ ảnh hưởng các ô cùng khối từ $p$ về trái, tính lại $O(B)$.

Ví dụNhững Bước Nhảy Thoát Mảng

Đề. $n \le 10^5$ ô, ô $i$ có $a_i \ge 1$, đứng ở $i$ thì nhảy tới $i + a_i$, dừng khi vượt $n$. $m \le 10^5$ thao tác: gán $a_p = x$, hoặc bắt đầu ở $p$ và in ô cuối cùng còn trong mảng cùng tổng số bước nhảy.

Lời giải. Chia ô thành khối dài $\sqrt n$. Với mỗi ô $i$ giữ ba thứ: nxt[i] là ô đầu tiên ngoài khối mà đường nhảy từ $i$ tới, cnt[i] là số bước để tới đó, lst[i] là ô cuối cùng trong khối trên đường đi. Câu hỏi đi theo nxt, mỗi bước qua ít nhất một khối. Gán $a_p$ chỉ ảnh hưởng các ô cùng khối và đứng trước $p$. Với ví dụ, khối dài 2: từ ô 1 đường đi $1 \to 3 \to 4 \to 6 \to 10$ qua ba lần nhảy theo nxt.

Bước 1: tính một ô. Nhảy một bước tới $j = i + a_i$. Ra ngoài khối (hoặc ngoài mảng) thì $i$ rời khối sau 1 bước và ô cuối trong khối là chính $i$. Còn trong khối thì kế thừa từ $j$, cộng thêm 1 bước.

void calc(ll i) {
    ll j = i + a[i];
    if (j > n || id[j] != id[i]) {
        nxt[i] = j;
        cnt[i] = 1;
        lst[i] = i;
    } else {
        nxt[i] = nxt[j];
        cnt[i] = cnt[j] + 1;
        lst[i] = lst[j];
    }
}

Bước 2: dựng và sửa. Dựng ban đầu duyệt $i$ từ $n$ về 1, nên $j > i$ luôn đã tính. Gán $a_p$ thì tính lại từ $p$ về đầu khối, $O(B)$.

for (ll i = n; i >= 1; i--) calc(i);

cin >> a[p];
for (ll i = p; i >= L[id[p]]; i--) calc(i);

Bước 3: câu hỏi. Cộng cnt, nhớ lst của bước cuối để in ô cuối cùng còn trong mảng.

ll steps = 0, last = p;
while (p <= n) {
    steps += cnt[p];
    last = lst[p];
    p = nxt[p];
}

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

const ll N = 1e5 + 5;
ll n, m, B, a[N], id[N], L[N], nxt[N], cnt[N], lst[N];

void calc(ll i) {
    ll j = i + a[i];
    if (j > n || id[j] != id[i]) {
        nxt[i] = j;
        cnt[i] = 1;
        lst[i] = i;
    } else {
        nxt[i] = nxt[j];
        cnt[i] = cnt[j] + 1;
        lst[i] = lst[j];
    }
}

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

    cin >> n >> m;
    B = max(1LL, (ll)sqrt(n));
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        id[i] = (i - 1) / B;
        if (!L[id[i]]) L[id[i]] = i;
    }
    for (ll i = n; i >= 1; i--) calc(i);
    while (m--) {
        ll t, p;
        cin >> t >> p;
        if (t == 0) {
            cin >> a[p];
            for (ll i = p; i >= L[id[p]]; i--) calc(i);
            continue;
        }
        ll steps = 0, last = p;
        while (p <= n) {
            steps += cnt[p];
            last = lst[p];
            p = nxt[p];
        }
        cout << last << ' ' << steps << '\n';
    }
}

Input6 5
2 3 1 2 1 4
1 1
0 3 4
1 1
1 2
0 6 1

Output6 4
3 2
6 3

Gán $O(\sqrt n)$, câu hỏi $O(\sqrt n)$ vì qua tối đa $\sqrt n$ khối.

Chia căn theo bậc trên đồ thị

Mục này dùng vài chữ của chương 3: đồ thị gồm các đỉnh và các cạnh nối hai đỉnh, bậc của một đỉnh là số cạnh nối với nó, và mỗi cạnh góp 1 vào bậc của cả hai đầu nên tổng mọi bậc là $2m$. Vì vậy đồ thị $m$ cạnh có không quá $2m / S$ đỉnh bậc lớn hơn $S$. Gọi chúng là đỉnh nặng, còn lại là đỉnh nhẹ. Duyệt hàng xóm của một đỉnh nhẹ tốn không quá $S$; đỉnh nặng thì ít, có thể giữ cho mỗi đỉnh nặng một bảng hay một bộ đếm riêng. Với $S = \sqrt m$ cả hai phía đều $O(\sqrt m)$.

Một cách dùng gọn: hướng mỗi cạnh từ đầu có bậc nhỏ hơn sang đầu có bậc lớn hơn (bằng nhau thì theo chỉ số). Đồ thị thành không có chu trình, và mỗi đỉnh có không quá $\sqrt{2m}$ cạnh đi ra: một đỉnh có $d$ cạnh đi ra thì cả $d$ hàng xóm đó có bậc ít nhất bằng nó, tức ít nhất $d$, nên $d \cdot d \le 2m$.

Ví dụTam Giác Trong Mạng Lưới

Đề. Đồ thị đơn $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh. Đếm số tam giác.

Lời giải. Hướng mỗi cạnh từ đầu có bậc nhỏ hơn sang đầu bậc lớn hơn (bằng nhau thì theo chỉ số); đồ thị hướng này không có chu trình. Mỗi tam giác có đúng một đỉnh mà cả hai cạnh của tam giác đều đi ra từ nó, nên được đếm đúng một lần ở đỉnh đó. Mỗi đỉnh có không quá $\sqrt{2m}$ cạnh đi ra: đỉnh có $d$ cạnh ra thì mỗi đỉnh nó đi tới có bậc ít nhất $d$, nên $d \cdot d \le 2m$.

Bước 1: đếm bậc rồi hướng cạnh.

for (ll i = 1; i <= m; i++) {
    ll u = eu[i], v = ev[i];
    if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v);
    g[u].push_back(v);
}

Bước 2: đếm tam giác ở đỉnh có hai cạnh ra. Đánh dấu các đỉnh $u$ đi tới bằng mark[v] = u; dùng chính $u$ làm dấu nên khỏi xóa mảng giữa các lượt. Với mỗi $v$ mà $u$ đi tới, mỗi $w$ mà $v$ đi tới và đã được đánh dấu là một tam giác $(u, v, w)$.

for (ll u = 1; u <= n; u++) {
    for (ll v : g[u]) mark[v] = u;
    for (ll v : g[u])
        for (ll w : g[v])
            if (mark[w] == u) ans++;
}

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

const ll N = 1e5 + 5, M = 2e5 + 5;
ll n, m, deg[N], eu[M], ev[M], mark[N];
vector<ll> g[N];

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

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        deg[eu[i]]++;
        deg[ev[i]]++;
    }
    for (ll i = 1; i <= m; i++) {
        ll u = eu[i], v = ev[i];
        if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v);
        g[u].push_back(v);
    }
    ll ans = 0;
    for (ll u = 1; u <= n; u++) {
        for (ll v : g[u]) mark[v] = u;
        for (ll v : g[u])
            for (ll w : g[v])
                if (mark[w] == u) ans++;
    }
    cout << ans << '\n';
}

Input5 6
1 2
2 3
1 3
3 4
4 5
3 5

Output2

Mỗi cạnh $u \to v$ tốn số cạnh ra của $v$, không quá $\sqrt{2m}$: tổng $O(m \sqrt m)$, khoảng $10^8$ phép đơn giản.