Xử lý truy vấn offline

Xử lý truy vấn offline là nhóm kỹ thuật dành cho các bài cho trước toàn bộ $Q$ truy vấn: thay vì trả lời lần lượt theo thứ tự đề cho, ta đọc hết truy vấn, sắp xếp lại chúng theo một thứ tự có lợi (theo đầu mút phải, theo ngưỡng, theo thời gian ngược...) rồi dùng một cấu trúc dữ liệu đơn giản (Fenwick, DSU) quét một lượt. Nhiều bài mà cách trả lời từng truy vấn độc lập tốn $O(NQ)$, hoặc cần cấu trúc bền vững (persistent) phức tạp, trở thành $O((N+Q)\log N)$ chỉ với một cây Fenwick hay một DSU vài dòng.

Online và offline

• Online: phải trả lời truy vấn $i$ trước khi được biết truy vấn $i+1$. Ví dụ bài tương tác, hoặc đề "mã hóa" truy vấn bằng đáp án trước: $l=l^{\prime }\oplus \text{last}$, $r=r^{\prime }\oplus \text{last}$ với $\text{last}$ là đáp án vừa in.
• Offline: toàn bộ truy vấn nằm sẵn trong input. Ta được phép đọc hết, trả lời theo bất kỳ thứ tự nào, lưu đáp án vào mảng ans[id] rồi cuối cùng in theo thứ tự gốc.

Khi nào được phép xử lý offline

Chỉ cần hai điều kiện:

1. Biết trước mọi truy vấn (không có tương tác, không mã hóa bằng đáp án trước).
2. Đáp án của truy vấn trước không làm thay đổi dữ liệu mà truy vấn sau nhìn thấy. Các truy vấn "chỉ hỏi" trên dữ liệu tĩnh luôn thỏa. Nếu có thao tác cập nhật xen giữa, ta vẫn offline được nhưng phải coi thời điểm là một chiều dữ liệu (xem Kỹ thuật 3, 4, 5).

Hầu hết đề VOI và đề thi học sinh giỏi cho toàn bộ truy vấn trong input, nên offline là vũ khí rất hay dùng. Khi đọc đề, hãy tự hỏi: "nếu được chọn thứ tự trả lời, thứ tự nào làm bài toán dễ nhất?"

Vì sao sắp lại thứ tự giúp được

Một truy vấn thường có hai hoặc nhiều ràng buộc (đoạn $[l,r]$ và ngưỡng $x$; đỉnh $u,v$ và trọng số tối đa $w$...). Cấu trúc dữ liệu thông thường chỉ xử lý tốt một ràng buộc. Ý tưởng chung của mọi kỹ thuật dưới đây:

Sắp truy vấn theo một ràng buộc, rồi quét theo ràng buộc đó và chỉ thêm (không bao giờ bỏ) dữ liệu vào cấu trúc. Ràng buộc còn lại do cấu trúc dữ liệu lo.

"Chỉ thêm" là mấu chốt: Fenwick thêm dễ, DSU chỉ gộp được chứ không tách được. Sắp lại truy vấn chính là cách biến bài toán thành dạng "chỉ thêm".

Kỹ thuật 1: Sắp theo đầu mút phải, quét và Fenwick

Bài toán mẫu: cho mảng $a_1..a_N$, $Q$ truy vấn $(l,r)$: đếm số giá trị phân biệt trong $a_l..a_r$. Không có cập nhật.

Ý tưởng: chỉ giữ lần xuất hiện cuối

Đếm trực tiếp mỗi truy vấn tốn $O(N)$. Khó ở chỗ một giá trị lặp nhiều lần trong đoạn chỉ được đếm một lần. Ta chọn một đại diện duy nhất cho mỗi giá trị: lần xuất hiện gần $r$ nhất (xuất hiện cuối cùng tính tới $r$).

Cố định $r$. Đánh dấu $mark[i]=1$ nếu $i$ là lần xuất hiện cuối cùng của $a_i$ trong $a_1..a_r$, ngược lại $0$. Khi đó với mọi $l\le r$:

$$\text{số giá trị phân biệt trong }[l,r]=\sum _{i=l}^{r}mark[i].$$

Vì sao: một giá trị $v$ xuất hiện trong $[l,r]$ khi và chỉ khi lần xuất hiện cuối cùng của nó (tính tới $r$) nằm trong $[l,r]$. Nếu lần cuối ở vị trí $p\ge l$ thì $v$ có mặt và được đếm đúng một lần tại $p$; nếu $p<l$ thì mọi lần xuất hiện của $v$ đều $<l$, $v$ không có trong đoạn.

Chọn "lần cuối" chứ không phải "lần đầu" vì ta sẽ quét $r$ tăng dần: khi $r$ tăng, lần cuối của $a_r$ dời sang $r$, chỉ cần tắt một dấu cũ và bật một dấu mới. Còn "lần đầu" trong $[l,r]$ lại phụ thuộc $l$, thay đổi theo từng truy vấn.

Vậy: sắp truy vấn theo $r$, quét $r=1..N$, cập nhật mark bằng Fenwick (tắt vị trí cũ, bật vị trí $r$), rồi trả lời mọi truy vấn có đầu mút phải bằng $r$ bằng một phép tính tổng đoạn.

Ví dụ chạy tay

$a=[1,2,1,3,2]$ (chỉ số từ 1), truy vấn $Q_0=(1,3)$, $Q_1=(2,5)$, $Q_2=(4,5)$. Nhóm theo $r$: $r=3$ có $Q_0$; $r=5$ có $Q_1,Q_2$.

vị trí:          1  2  3  4  5
a:               1  2  1  3  2

r=1  a=1 mới           mark = [1  0  0  0  0]
r=2  a=2 mới           mark = [1  1  0  0  0]
r=3  a=1, cũ ở 1:      tắt 1, bật 3
                       mark = [0  1  1  0  0]
     Q0 (1,3): tổng mark[1..3] = 0+1+1 = 2      {1, 2}
r=4  a=3 mới           mark = [0  1  1  1  0]
r=5  a=2, cũ ở 2:      tắt 2, bật 5
                       mark = [0  0  1  1  1]
     Q1 (2,5): tổng mark[2..5] = 0+1+1+1 = 3    {2, 1, 3}
     Q2 (4,5): tổng mark[4..5] = 1+1   = 2      {3, 2}

Để ý ở $r=5$: giá trị $2$ chỉ còn dấu ở vị trí $5$. $Q_1$ bắt đầu từ $2$ nhưng vẫn đếm đúng giá trị $2$ nhờ dấu ở vị trí $5$.

Cài đặt C++

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

struct Fenwick {
    int n; vector<int> t;
    Fenwick(int n) : n(n), t(n + 1, 0) {}
    void add(int i, int v) { for (; i <= n; i += i & -i) t[i] += v; }
    int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
};

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    // group queries by right endpoint
    vector<vector<pair<int,int>>> byRight(n + 1);   // byRight[r] = {(l, id)}
    for (int j = 0; j < q; j++) {
        int l, r; scanf("%d %d", &l, &r);
        byRight[r].push_back({l, j});
    }
    map<int,int> last;              // value -> latest position seen so far
    Fenwick fw(n);
    vector<int> ans(q);
    for (int r = 1; r <= n; r++) {
        auto it = last.find(a[r]);
        if (it != last.end()) fw.add(it->second, -1);   // old occurrence no longer "last"
        fw.add(r, +1);
        last[a[r]] = r;
        for (auto [l, id] : byRight[r])
            ans[id] = fw.sum(r) - fw.sum(l - 1);        // marks inside [l, r]
    }
    for (int j = 0; j < q; j++) printf("%d\n", ans[j]);
}

Thay vì sắp truy vấn bằng sort, code gom chúng vào byRight[r] (sắp đếm, $O(N+Q)$). Có thể thay map bằng nén tọa độ và một mảng last[] để nhanh hơn.

Cài đặt Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    a = [0] + [int(x) for x in data[2:2 + n]]
    by_right = [[] for _ in range(n + 1)]
    pos = 2 + n
    for j in range(q):
        l, r = int(data[pos]), int(data[pos + 1]); pos += 2
        by_right[r].append((l, j))

    tree = [0] * (n + 1)
    def add(i, v):
        while i <= n:
            tree[i] += v
            i += i & -i
    def prefix(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    last = {}
    ans = [0] * q
    for r in range(1, n + 1):
        if a[r] in last:
            add(last[a[r]], -1)      # old occurrence is no longer the latest
        add(r, 1)
        last[a[r]] = r
        for l, j in by_right[r]:
            ans[j] = prefix(r) - prefix(l - 1)
    sys.stdout.write("\n".join(map(str, ans)) + "\n")

main()

Khuôn tổng quát: quét $r$ từ trái sang phải, duy trì một mảng $f_r(l)$ "đáp án nếu đoạn bắt đầu ở $l$" trên cấu trúc dữ liệu; mỗi lần $r$ tăng chỉ cập nhật vài điểm hoặc vài đoạn của $f$; truy vấn $(l,r)$ là một phép hỏi trên $f_r$. Khi phép cập nhật là cộng đoạn và cần min/đếm số 0, thay Fenwick bằng Segment Tree có lazy.

Kỹ thuật 2: Sắp theo ngưỡng rồi thêm dần

Nhiều truy vấn có dạng "chỉ xét những phần tử/cạnh có giá trị $\le x$". Nếu sắp truy vấn theo $x$ tăng dần, tập phần tử được phép chỉ lớn lên: ta sắp luôn các phần tử theo giá trị, dùng một con trỏ thêm dần (giống hai con trỏ trên hai mảng đã sắp xếp).

2a. Đếm số phần tử $\le x$ trong đoạn

Truy vấn $(l,r,x)$: đếm $i\in [l,r]$ có $a_i\le x$. Hai ràng buộc: vị trí trong $[l,r]$ và giá trị $\le x$. Sắp theo $x$ lo ràng buộc giá trị; Fenwick trên vị trí lo ràng buộc đoạn.

$a=[5,1,4,2,3]$, truy vấn $A=(1,5,x=3)$, $B=(2,4,x=1)$, $C=(1,3,x=4)$.

Phần tử sắp theo giá trị: (1,@2) (2,@4) (3,@5) (4,@3) (5,@1)
Truy vấn sắp theo x:      B(x=1)  A(x=3)  C(x=4)

vị trí:                 1  2  3  4  5
B x=1: bật @2         [ 0  1  0  0  0 ]   đếm [2..4] = 1
A x=3: bật @4, @5     [ 0  1  0  1  1 ]   đếm [1..5] = 3
C x=4: bật @3         [ 0  1  1  1  1 ]   đếm [1..3] = 2
                                          (phần tử 5 ở @1 không bao giờ bật)

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

struct Fenwick {
    int n; vector<int> t;
    Fenwick(int n) : n(n), t(n + 1, 0) {}
    void add(int i, int v) { for (; i <= n; i += i & -i) t[i] += v; }
    int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
};

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    vector<pair<int,int>> elems(n);            // (value, position)
    for (int i = 1; i <= n; i++) { scanf("%d", &elems[i - 1].first); elems[i - 1].second = i; }
    struct Query { int l, r, x, id; };
    vector<Query> qs(q);
    for (int j = 0; j < q; j++) { scanf("%d %d %d", &qs[j].l, &qs[j].r, &qs[j].x); qs[j].id = j; }

    sort(elems.begin(), elems.end());
    sort(qs.begin(), qs.end(), [](const Query& A, const Query& B) { return A.x < B.x; });

    Fenwick fw(n);
    vector<int> ans(q);
    size_t p = 0;
    for (auto& Q : qs) {
        // activate every element with value <= x (pointer only moves forward)
        while (p < elems.size() && elems[p].first <= Q.x) fw.add(elems[p++].second, 1);
        ans[Q.id] = fw.sum(Q.r) - fw.sum(Q.l - 1);
    }
    for (int j = 0; j < q; j++) printf("%d\n", ans[j]);
}

Cùng khuôn này đếm điểm trong "góc" $\{(p,q):p\le a,q\le b\}$: sắp điểm theo $p$, truy vấn theo $a$, Fenwick trên $q$ đã nén. Đó là bài toán đếm điểm trội hai chiều (2D dominance), gặp lại ở nhiều đề (xem voi24_impev bên dưới).

2b. DSU theo ngưỡng: "chỉ đi qua cạnh có trọng số $\le w$"

Truy vấn dạng "hai đỉnh có đi được tới nhau chỉ bằng cạnh $\le w$ không", "thành phần chứa $u$ có bao nhiêu đỉnh", "có bao nhiêu cặp đỉnh nối được"... Nếu từng truy vấn phải dựng lại đồ thị con thì tốn $O(Q·M)$. Sắp truy vấn theo $w$ tăng dần và thêm cạnh theo trọng số tăng dần bằng DSU: đúng là chạy Kruskal và dừng lại trả lời ở giữa chừng. DSU không tách được cạnh, nhưng ở đây ta không bao giờ cần tách.

Ví dụ: cây $N$ đỉnh, mỗi truy vấn $q$ hỏi số cặp $(u,v)$ mà cạnh lớn nhất trên đường đi $\le q$. Hai đỉnh thỏa khi và chỉ khi chúng cùng thành phần sau khi thêm mọi cạnh $\le q$. Gộp hai thành phần cỡ $s_1,s_2$ tạo thêm đúng $s_1·s_2$ cặp mới.

Cây: 1 -(1)- 2 -(2)- 3        Truy vấn: q = 1, q = 3, q = 2

Truy vấn sắp theo q: 1, 2, 3
q=1: thêm cạnh (1,2,w=1): {1,2} {3}     cặp = 1*1 = 1
q=2: thêm cạnh (2,3,w=2): {1,2,3}       cặp = 1 + 2*1 = 3
q=3: không còn cạnh                      cặp = 3
In theo thứ tự gốc: 1 3 3

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

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    // returns the number of new connected pairs created by this union
    long long unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return 0;
        if (sz[a] < sz[b]) swap(a, b);
        long long created = 1LL * sz[a] * sz[b];
        p[b] = a; sz[a] += sz[b];
        return created;
    }
};

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<array<int,3>> edges(n - 1);          // (w, u, v)
    for (auto& e : edges) scanf("%d %d %d", &e[1], &e[2], &e[0]);
    vector<pair<int,int>> qs(m);                // (threshold, id)
    for (int j = 0; j < m; j++) { scanf("%d", &qs[j].first); qs[j].second = j; }

    sort(edges.begin(), edges.end());
    sort(qs.begin(), qs.end());

    DSU dsu(n);
    long long pairs = 0;
    vector<long long> ans(m);
    size_t p = 0;
    for (auto [w, id] : qs) {
        while (p < edges.size() && edges[p][0] <= w) {   // add every edge with weight <= w
            pairs += dsu.unite(edges[p][1], edges[p][2]);
            p++;
        }
        ans[id] = pairs;
    }
    for (int j = 0; j < m; j++) printf("%lld ", ans[j]);
    printf("\n");
}

Truy vấn "minimax giữa $u$ và $v$" (cạnh lớn nhất nhỏ nhất trên đường đi) cũng trả lời offline theo đúng cách này; phiên bản online cần dựng cây khung rồi nhảy nhị phân, xem cây khung nhỏ nhất.

Kỹ thuật 3: Xử lý ngược thời gian (xóa thành thêm)

Bài toán mẫu: mảng $a_1..a_N$ không âm, lần lượt phá hủy các vị trí theo hoán vị $p_1..p_N$. Sau mỗi bước, in tổng lớn nhất của một đoạn liên tiếp chưa bị phá.

Đi xuôi thì các đoạn bị cắt ra, mà DSU không tách được. Nhưng ta biết trước toàn bộ thứ tự phá, nên có thể chạy phim ngược: bắt đầu từ mảng trống (trạng thái sau bước $N$), rồi lần lượt khôi phục $p_N,p_{N-1},\dots ,p_1$. Xóa biến thành thêm, cắt đoạn biến thành gộp đoạn, đúng sở trường của DSU.

Ba điều cần nắm:

• Đáp án sau bước $i$ chính là trạng thái trước khi khôi phục $p_i$ trong lượt ngược. Nên ghi ans[i] trước, rồi mới khôi phục.
• Trong lượt ngược, tập vị trí còn sống chỉ lớn lên, nên mọi đoạn hợp lệ ở bước trước vẫn hợp lệ ở bước sau. Vì vậy đáp án trong lượt ngược không bao giờ giảm: chỉ cần một biến best, không cần multiset. Điều này đúng bất kể dấu của $a_i$.
• Điều kiện $a_i\ge 0$ cần ở chỗ khác: khi mọi số không âm, đoạn con có tổng lớn nhất nằm trong một đoạn còn sống chính là cả đoạn đó, nên mỗi gốc DSU chỉ cần lưu tổng segSum. Nếu mảng có số âm thì code dưới đây sai; khi đó mỗi đoạn phải lưu thêm tổng tiền tố lớn nhất, tổng hậu tố lớn nhất và tổng đoạn con lớn nhất, rồi kết hợp các giá trị này khi ghép hai đoạn.

Ví dụ chạy tay

$a=[1,3,2,5]$, thứ tự phá $3,4,1,2$. Kỳ vọng in $5,4,3,0$.

Lượt ngược (· = chưa khôi phục):        vị trí 1  2  3  4

i=4: ans[4] = best = 0
     khôi phục 2:   ·  [3]  ·   ·        best = 3
i=3: ans[3] = 3
     khôi phục 1:  [1   3]  ·   ·        gộp với 2, tổng 4, best = 4
i=2: ans[2] = 4
     khôi phục 4:  [1   3]  ·  [5]       best = 5
i=1: ans[1] = 5
     khôi phục 3:  [1   3   2   5]       gộp cả hai phía, tổng 11

In ans[1..4] = 5 4 3 0

Cài đặt

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

int n;
vector<int> par, sz;
vector<long long> segSum;        // sum of the segment whose root is this index
vector<bool> alive;

int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);   // union by size: attach the smaller tree
    par[b] = a;
    sz[a] += sz[b];
    segSum[a] += segSum[b];
}

int main() {
    scanf("%d", &n);
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    vector<int> order(n + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &order[i]);

    par.resize(n + 2); iota(par.begin(), par.end(), 0);
    sz.assign(n + 2, 1);
    segSum.assign(n + 2, 0);
    alive.assign(n + 2, false);  // sentinels 0 and n+1 stay dead

    vector<long long> ans(n + 1);
    long long best = 0;                // after all n deletions the answer is 0
    // go backwards: answer after step i is the state before restoring order[i]
    for (int i = n; i >= 1; i--) {
        ans[i] = best;
        int x = order[i];              // restore position x
        alive[x] = true;
        segSum[x] = a[x];
        if (alive[x - 1]) unite(x, x - 1);
        if (alive[x + 1]) unite(x, x + 1);
        best = max(best, segSum[find(x)]);   // segments only grow, so best never drops
    }
    for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
}

Trên đồ thị cũng vậy: "lần lượt xóa cạnh/đỉnh, sau mỗi lần hỏi số thành phần liên thông" được giải bằng cách thêm trước mọi cạnh không bao giờ bị xóa, rồi thêm ngược các cạnh bị xóa. Nếu đề trộn lẫn cả thêm và xóa một cách tùy ý, chạy ngược không giúp gì (xóa ngược lại thành thêm, thêm ngược lại thành xóa); khi đó cần DSU có hoàn tác và chia để trị theo thời gian.

Kỹ thuật 4: Chặt nhị phân song song (parallel binary search)

Dạng bài: có một dãy $K$ thao tác cập nhật theo thời gian, và $Q$ truy vấn, mỗi truy vấn hỏi "thời điểm sớm nhất mà điều kiện của tôi được thỏa". Điều kiện phải đơn điệu theo thời gian: đã thỏa ở thời điểm $t$ thì thỏa ở mọi $t^{\prime }>t$ (ví dụ các thao tác chỉ cộng số không âm, chỉ thêm cạnh).

Ví dụ cụ thể: mảng $N$ số ban đầu bằng $0$, thao tác $t$ cộng $v_t\ge 0$ vào đoạn $[L_t,R_t]$. Truy vấn $j$ hỏi thao tác đầu tiên mà sau nó tổng $a[q{l}_j..q{r}_j]\ge nee{d}_j$.

Ý tưởng

Với một truy vấn, ta chặt nhị phân trên $t$: mỗi bước "mô phỏng tới $t=mid$ rồi kiểm tra", mất $O(K\log N)$ cho mô phỏng, tổng $O(K\log N\log K)$ cho một truy vấn, nhân $Q$ thì quá chậm.

Nhận xét: phần tốn kém là mô phỏng dòng thời gian, và mọi truy vấn dùng chung một dòng thời gian. Vậy cho tất cả truy vấn chặt nhị phân cùng lúc:

• Mỗi truy vấn giữ khoảng $[l{o}_j,h{i}_j]$ chứa đáp án (dùng $hi=K+1$ nghĩa là "không bao giờ").
• Mỗi vòng: mỗi truy vấn chưa chốt chọn $mi{d}_j$ và được bỏ vào "giỏ" $mi{d}_j$. Rồi mô phỏng một lần từ thời điểm $1$ tới $K$; ngay sau thao tác $t$, kiểm tra mọi truy vấn trong giỏ $t$ và thu hẹp khoảng của chúng.
• Mỗi vòng khoảng của mọi truy vấn giảm một nửa, nên sau $\lceil {\log }_2(K+1)\rceil$ vòng mọi truy vấn đều chốt.

Ví dụ chạy tay

$N=3$, $K=4$ thao tác cộng đoạn và $3$ truy vấn:

Thao tác (L R v):          Mảng a sau thao tác t:
t=1: 1 1 1                 t=1: [1 0 0]
t=2: 2 3 2                 t=2: [1 2 2]
t=3: 1 2 1                 t=3: [2 3 2]
t=4: 3 3 3                 t=4: [2 3 5]

Truy vấn (ql qr need):  A = (1 2 3)   B = (3 3 4)   C = (1 1 5)

Khoảng ban đầu của mọi truy vấn là $[1,5]$ ($5=K+1$ nghĩa là "không bao giờ"). Mỗi vòng, $mid=\lfloor (lo+hi)/2\rfloor$; "thỏa" thì $hi=mid$, "chưa" thì $lo=mid+1$.

Vòng 1: mid A=3 B=3 C=3   (mô phỏng t=1..4, kiểm tra ở t=3, a=[2 3 2])
        A: a1+a2 = 5 >= 3  thỏa -> [1,3]
        B: a3    = 2 <  4  chưa -> [4,5]
        C: a1    = 2 <  5  chưa -> [4,5]
Vòng 2: mid A=2 B=4 C=4
        A ở t=2, a=[1 2 2]: a1+a2 = 3 >= 3  thỏa -> [1,2]
        B ở t=4, a=[2 3 5]: a3    = 5 >= 4  thỏa -> [4,4]
        C ở t=4, a=[2 3 5]: a1    = 2 <  5  chưa -> [5,5]
Vòng 3: mid A=1
        A ở t=1, a=[1 0 0]: a1+a2 = 1 <  3  chưa -> [2,2]
Kết quả: A=2, B=4, C=5 tức "không bao giờ" (code in -1)

Đủ $3=\lceil {\log }_{2}5\rceil$ vòng. Mỗi vòng chỉ có một lần mô phỏng trọn dòng thời gian, dù có bao nhiêu truy vấn. Input của ví dụ cho code dưới đây là dòng 3 4 3, tiếp theo bốn dòng thao tác và ba dòng truy vấn như trên; output là 2, 4, -1.

Cài đặt

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

// Fenwick with range add, range sum (two internal trees)
struct RangeFenwick {
    int n; vector<ll> b1, b2;
    RangeFenwick(int n) : n(n), b1(n + 2), b2(n + 2) {}
    void reset() { fill(b1.begin(), b1.end(), 0); fill(b2.begin(), b2.end(), 0); }
    void upd(vector<ll>& b, int i, ll v) { for (; i <= n; i += i & -i) b[i] += v; }
    ll qry(const vector<ll>& b, int i) { ll s = 0; for (; i > 0; i -= i & -i) s += b[i]; return s; }
    void rangeAdd(int l, int r, ll v) {
        upd(b1, l, v); upd(b1, r + 1, -v);
        upd(b2, l, v * (l - 1)); upd(b2, r + 1, -v * r);
    }
    ll prefix(int i) { return qry(b1, i) * i - qry(b2, i); }
    ll rangeSum(int l, int r) { return prefix(r) - prefix(l - 1); }
};

int main() {
    int n, k, q;
    scanf("%d %d %d", &n, &k, &q);
    vector<int> opL(k + 1), opR(k + 1); vector<ll> opV(k + 1);
    for (int i = 1; i <= k; i++) scanf("%d %d %lld", &opL[i], &opR[i], &opV[i]);
    vector<int> ql(q), qr(q); vector<ll> need(q);
    for (int j = 0; j < q; j++) scanf("%d %d %lld", &ql[j], &qr[j], &need[j]);

    // answer of query j lies in [lo[j], hi[j]]; value k + 1 means "never"
    vector<int> lo(q, 1), hi(q, k + 1);
    RangeFenwick fw(n);
    vector<vector<int>> bucket(k + 2);
    while (true) {
        bool changed = false;
        for (int t = 1; t <= k; t++) bucket[t].clear();
        for (int j = 0; j < q; j++)
            if (lo[j] < hi[j]) { bucket[(lo[j] + hi[j]) / 2].push_back(j); changed = true; }
        if (!changed) break;
        fw.reset();
        for (int t = 1; t <= k; t++) {           // one full replay of the timeline
            fw.rangeAdd(opL[t], opR[t], opV[t]);
            for (int j : bucket[t]) {
                if (fw.rangeSum(ql[j], qr[j]) >= need[j]) hi[j] = t;   // already satisfied at t
                else lo[j] = t + 1;
            }
        }
    }
    for (int j = 0; j < q; j++) printf("%d\n", lo[j] <= k ? lo[j] : -1);
}

Cũng có thể cài bằng đệ quy chia để trị solve(lo, hi, danh sách truy vấn): áp dụng các thao tác $lo..mid$, chia truy vấn thành nhóm "đã thỏa" (đệ quy nửa trái) và "chưa thỏa" (trừ đi phần đã góp rồi đệ quy nửa phải). Bản lặp theo vòng ở trên dễ cài và dễ kiểm tra hơn.

Kỹ thuật 5: Các kỹ thuật offline có trang riêng

Ba kỹ thuật dưới đây cũng thuộc họ offline nhưng đủ lớn để có trang riêng; ở đây chỉ nêu khi nào nghĩ tới chúng.

• Thuật toán Mo: truy vấn đoạn $[l,r]$ trên mảng tĩnh mà thông tin không cộng/trừ được theo tiền tố nhưng thêm/bớt một phần tử ở hai đầu thì rẻ (đếm cặp bằng nhau, tần suất, mode...). Sắp truy vấn theo (khối của $l$, $r$), tổng quãng đường con trỏ $O((N+Q)\sqrt{N})$. Nếu thông tin lại có dạng "đại diện duy nhất" như số giá trị phân biệt thì Kỹ thuật 1 nhanh hơn ($O((N+Q)\log N)$).
• CDQ (chia để trị theo thời gian): có cả cập nhật và truy vấn xen kẽ, mỗi cập nhật ảnh hưởng tới mọi truy vấn sau nó, và ảnh hưởng đó cộng dồn được. Chia đôi dãy thao tác, tính ảnh hưởng của nửa trái lên nửa phải bằng quét + Fenwick. Mỗi lớp CDQ "gỡ" được một chiều (thời gian), biến bài 3 chiều thành bài 2 chiều như Kỹ thuật 2a.
• DSU có hoàn tác, chia để trị theo thời gian: đồ thị có cả thêm và xóa cạnh, hỏi liên thông. Mỗi cạnh sống trong một khoảng thời gian, gắn khoảng đó lên cây phân đoạn trên trục thời gian, DFS cây phân đoạn với DSU "vào gộp, ra hoàn tác". Cùng khung đó còn giải các bài chia để trị trên đáp án đơn điệu với DSU.

Bảng chọn kỹ thuật

Độ phức tạp

Lý giải:

• Kỹ thuật 1: mỗi vị trí $r$ gây tối đa hai phép cập nhật Fenwick (tắt dấu cũ, bật dấu mới), mỗi truy vấn đúng hai phép tính tiền tố; mỗi phép $O(\log N)$.
• Kỹ thuật 2: con trỏ trên danh sách phần tử (hoặc cạnh) chỉ tiến, nên mỗi phần tử được thêm đúng một lần dù có bao nhiêu truy vấn; phần trội là hai lần sắp xếp ($O(N\log N)$ cho phần tử hoặc $O(M\log M)$ cho cạnh, $O(Q\log Q)$ cho truy vấn) và các phép Fenwick/DSU.
• Kỹ thuật 3: mỗi phần tử được khôi phục một lần, mỗi lần tối đa hai phép gộp DSU. Cận $\alpha (N)$ cần cả nén đường lẫn hợp theo kích thước (code ở trên có đủ hai); nếu chỉ nén đường mà gộp tùy ý thì cận chuẩn là $O(\log N)$ khấu hao mỗi thao tác.
• Kỹ thuật 4: có $\lceil {\log }_2(K+1)\rceil$ vòng; mỗi vòng reset cấu trúc ($O(N)$ với fill), dọn các giỏ ($O(K)$), mô phỏng lại $K$ thao tác (mỗi thao tác tốn $U$, ở ví dụ là $O(\log N)$) và kiểm tra mỗi truy vấn một lần (tốn $C$, ở ví dụ $O(\log N)$). Ví dụ trên chạy $O((N+(K+Q)\log N)\log K)$. Bộ nhớ không phụ thuộc số vòng vì mỗi vòng dựng lại cấu trúc từ đầu.

⚠️ Lỗi thường gặp

• In đáp án theo thứ tự đã sắp. Triệu chứng: sai từ test đầu tiên dù "thuật toán đúng". Luôn lưu id gốc của truy vấn trước khi sắp và ghi vào ans[id], in theo id tăng dần.
• Dùng offline cho bài bắt buộc online. Nếu $l,r$ của truy vấn sau được tính từ đáp án truy vấn trước (kiểu l ^= last), ta không thể đọc trước truy vấn. Phải chuyển sang cấu trúc online như Persistent Segment Tree.
• Sai dấu $<$ và $\le$ ở ngưỡng. Đề nói "cạnh có trọng số không vượt quá $w$" thì điều kiện thêm là <= w; "nhỏ hơn hẳn" thì < w. Khi nhiều phần tử và truy vấn trùng giá trị, sai dấu làm thiếu hoặc thừa đúng những phần tử bằng ngưỡng. Kiểm tra bằng một test có giá trị trùng.
• Chạy ngược nhưng ghi đáp án sai thời điểm. Đáp án "sau bước $i$" là trạng thái trước khi khôi phục $p_i$ trong lượt ngược. Ghi sau khi khôi phục sẽ lệch một bước. Đồng thời phải thêm sẵn mọi phần tử/cạnh không bao giờ bị xóa trước khi bắt đầu lượt ngược.
• Chạy ngược khi đề có cả thêm và xóa. Đảo thời gian chỉ đổi "xóa" thành "thêm" và ngược lại; nếu đề trộn cả hai thì lượt ngược vẫn có xóa. Dùng DSU hoàn tác thay thế.
• Chặt nhị phân song song mà quên reset cấu trúc. Mỗi vòng mô phỏng lại từ thời điểm $1$, nên Fenwick/DSU phải được làm sạch đầu mỗi vòng. Reset bằng fill $O(N)$ mỗi vòng là chấp nhận được ($O(N\log K)$ tổng cộng); đừng tạo lại vector trong vòng lặp trong cùng.
• Chặt nhị phân song song khi điều kiện không đơn điệu. Nếu thao tác có thể làm tổng giảm (cộng số âm, xóa cạnh) thì "đã thỏa ở $mid$" không suy ra "thỏa ở mọi $t>mid$", kết quả sai âm thầm. Kiểm tra tính đơn điệu trước khi dùng.
• Quên trường hợp "không bao giờ thỏa". Dùng biên $hi=K+1$ làm giá trị canh; nếu khởi tạo $hi=K$ thì truy vấn không bao giờ thỏa sẽ bị báo nhầm là $K$.
• Tràn số. Số cặp đỉnh liên thông tới $\left(\genfrac{}{}{0ex}{}{N}{2}\right)\approx 2·{10}^{10}$ với $N=2·{10}^5$; tổng đoạn trong Fenwick cộng đoạn dễ vượt $2^{31}$. Dùng long long cho đáp án và các mảng tổng.
• Fenwick với chỉ số 0 hoặc giá trị chưa nén. Fenwick đánh chỉ số từ $1$; gọi add(0, v) lặp vô hạn. Khi Fenwick đặt trên trục giá trị (tới ${10}^9$) phải nén tọa độ trước.

Biến thể / Mở rộng

• Quét theo đầu mút phải với cập nhật đoạn. Khi thêm phần tử $r$ làm thay đổi đáp án của cả một dải $l$ (ví dụ đếm đoạn con "đẹp" trong $[U,V]$), $f_r(l)$ được cập nhật bằng phép cộng đoạn và cần Segment Tree lazy, có khi phải thêm nhãn "cộng dồn theo thời gian" để đếm tổng qua mọi $r$.
• Offline trên cây. Truy vấn cây con trở thành truy vấn đoạn sau khi trải phẳng cây bằng Euler tour; khi đó Kỹ thuật 1 và 2 dùng nguyên vẹn. Nhiều truy vấn LCA cũng có thuật toán offline riêng (Tarjan) dùng DSU, xem LCA.
• Quét đường thẳng hình học. Kỹ thuật 2a chính là một sweep line một chiều: sự kiện "thêm điểm" và "trả lời truy vấn" được sắp chung theo một tọa độ; khi hai loại sự kiện trùng tọa độ, thứ tự xử lý quyết định dấu $<$ hay $\le$.
• Kết hợp nhiều lớp. Chặt nhị phân song song bên trong có thể là Kỹ thuật 2b (DSU thêm cạnh theo thời gian); CDQ lồng Kỹ thuật 2a; đếm điểm trội 3 chiều = CDQ + sắp theo chiều thứ hai + Fenwick chiều thứ ba.
• Chuyển offline thành online. Khi đề bắt buộc online, các cấu trúc bền vững lưu lại mọi "phiên bản" của lượt quét offline: phiên bản $r$ của Fenwick trong Kỹ thuật 1 chính là root[r] của Persistent Segment Tree. Hiểu bản offline trước thường là cách dễ nhất để thiết kế bản online.

Bài tập luyện

Luyện kỹ thuật

• Phá huỷ mảng (destarr) (Nâng cao) bài mẫu của Kỹ thuật 3: phá phần tử theo hoán vị cho trước, chạy ngược để các đoạn chỉ còn gộp lại bằng DSU.
• Truy vấn Số Giá trị Phân biệt (distvalq) (Nâng cao) bài mẫu của Kỹ thuật 1: gom truy vấn theo $r$, giữ dấu ở lần xuất hiện cuối trên Fenwick (cũng giải được bằng Mo nhưng chậm hơn).
• Truy vấn cặp đỉnh trên cây (trpairq) (Nâng cao) bài mẫu của Kỹ thuật 2b: sắp cạnh và truy vấn theo ngưỡng, mỗi lần gộp hai thành phần cỡ $s_1,s_2$ cộng thêm $s_1{s}_2$ cặp.
• Đếm số xuất hiện đúng bằng giá trị (elefarr) (Kỳ cựu) Kỹ thuật 1 nâng cao, dạng cộng đoạn, hỏi điểm: khi quét $r$, mỗi giá trị $x$ chỉ "đạt đúng $x$ lần" với $l$ nằm trong một khoảng giữa hai lần xuất hiện ($l\in (p_{k-x},p_{k-x+1}]$), nên mỗi bước cộng/trừ $1$ trên cả đoạn $l$ đó (cập nhật điểm trên mảng hiệu bằng Fenwick), rồi đáp án truy vấn $(l,r)$ là tổng tiền tố tại $l$ chứ không phải tổng đoạn như bài mẫu.
• Đánh Giá Độ Khó Đường Trượt (skilevel) (Chuyên gia) hỏi ngưỡng $D$ nhỏ nhất để thành phần chứa mỗi điểm xuất phát đạt $T$ ô: luyện được cả chặt nhị phân song song (Kỹ thuật 4, mô phỏng là thêm cạnh lưới theo chênh lệch tăng dần bằng DSU) lẫn cách chốt đáp án ngay trong lúc gộp.

Đề VOI

• Cải thiện đánh giá (voi24_impev) (Nâng cao) VOI 2024: sau khi có khoảng cách ngắn nhất, hãy tìm cách quy mỗi phương án về việc đếm điểm $(d_1,d_2)$ nằm trong một góc; khi đó mọi câu hỏi có thể trả lời chung một lượt bằng Kỹ thuật 2a.
• Tất niên (voi26_tet) (Kỳ cựu) VOI 2026: đĩa chỉ bị lấy đi, nên hãy đặt đĩa trở lại theo thứ tự ngược (Kỹ thuật 3) để các đoạn chỉ còn ghép lại; phần còn lại là một công thức đếm và cách cập nhật nó khi ghép hai đoạn.
• Quà Noel (voi26_gift) (Chuyên gia) VOI 2026: mọi câu hỏi có sẵn trong input nên bài không bắt buộc online. Lời giải chính thức dùng cây phân đoạn bền vững để trả lời từng câu; offline thuần (sắp câu hỏi theo $T$, chuyển dần loại quà có $S_i\le T$ sang "đầy" trên Fenwick theo thứ tự $W$ như Kỹ thuật 2) giải được subtask chỉ có loại 1, còn loại 2 (tìm $T$ lớn nhất, điều kiện đơn điệu theo $T$) cần thêm chặt nhị phân song song (Kỹ thuật 4) hoặc cấu trúc bền vững.
• Bài đăng (voi26_post) (Chuyên gia) VOI 2026: quét $R$ tăng dần và trả lời truy vấn $(U,V)$ tại $R=V$ (khuôn Kỹ thuật 1), nhưng $f_R(L)$ thay đổi theo đoạn nên cần cây phân đoạn lazy đếm số vị trí bằng $0$ cộng dồn qua thời gian.