Two Pointers

IĐoạn dài nhất: cửa sổ trượt

Trước hết, ta xét cách làm dễ nghĩ ra nhất. Đánh số các việc từ $1$ tới $n$, việc thứ $i$ cần $a_i$ đơn vị thời gian. Đoạn gồm các việc từ $l$ tới $r$ được viết là $[l, r]$; khi $l = r + 1$, đoạn không có việc nào và có độ dài $0$.

Với mỗi vị trí $r$, ta tìm đoạn dài nhất kết thúc tại $r$: bắt đầu từ cả đoạn $[1, r]$, rồi lần lượt bỏ các việc ở đầu đoạn cho tới khi tổng không còn vượt quá $T$. Vì ta chỉ bỏ đúng số việc cần thiết, đoạn còn lại là đoạn dài nhất kết thúc tại $r$ có tổng không quá $T$. Đáp án là đoạn dài nhất trong tất cả các đoạn tìm được.

ll ans = 0;
for (ll r = 1; r <= n; r++) {
    ll l = 1, sum = 0;
    for (ll i = 1; i <= r; i++) sum += a[i];
    while (sum > t) sum -= a[l++];
    ans = max(ans, r - l + 1);
}

Độ phức tạp: $O(n^2)$, với $n = 10^5$ cần khoảng $10^{10}$ phép tính.

Cách làm này cho kết quả đúng nhưng chạy chậm, vì với mỗi $r$, chương trình lại tính tổng từ đầu và bỏ các việc từ đầu. Máy chấm thường chỉ làm được khoảng $10^8$ phép tính mỗi giây, nên $10^{10}$ phép tính vượt xa giới hạn thời gian.

Ta có thể thấy được điểm lãng phí của cách làm trên. Giả sử khi xét $r$, ta đã phải bỏ các việc $1, 2, \dots, l - 1$ ở đầu đoạn, tức là mọi đoạn bắt đầu trước $l$ và kết thúc tại $r$ đều có tổng vượt $T$. Khi chuyển sang $r + 1$, mỗi đoạn như vậy có thêm việc $r + 1$, tổng chỉ có thể lớn hơn, nên vẫn vượt $T$. Vì vậy các việc $1, 2, \dots, l - 1$ vẫn sẽ phải bỏ, và cách làm trên đang bỏ lại chúng ở mỗi bước. Ta có thể giữ lại kết quả của bước trước: giữ nguyên l và sum (tổng của đoạn $[l, r]$), chỉ cộng thêm $a_{r+1}$, rồi tiếp tục bỏ việc từ vị trí $l$ hiện tại nếu tổng vẫn vượt $T$.

Trong code, ta chỉ cần sửa hai chỗ: đưa l và sum ra ngoài vòng for, và bỏ vòng tính lại tổng từ đầu.

ll l = 1, sum = 0, ans = 0;
for (ll r = 1; r <= n; r++) {
    sum += a[r];
    while (sum > t) sum -= a[l++];
    ans = max(ans, r - l + 1);
}

Độ phức tạp: $O(n)$, với $n = 10^5$ cần khoảng $2 \cdot 10^5$ phép tính.

Đoạn $[l, r]$ trong cách làm này giống như một khung nhìn lướt trên dãy: $r$ đưa thêm việc vào khung, $l$ đưa bớt việc ra khỏi khung, và cả khung chỉ di chuyển sang phải. Vì vậy, đoạn $[l, r]$ thường được gọi là cửa sổ (window), còn cách làm này được gọi là cửa sổ trượt (sliding window). Từ đây về sau, ta gọi $l$ là đầu trái và $r$ là đầu phải của cửa sổ.

Ta thử chạy tay với dãy $2, 3, 1, 2, 4, 3, 1, 5$ và $T = 10$. Đầu phải lần lượt đưa $2, 3, 1, 2$ vào cửa sổ: tổng là $8$, chưa vượt $T$, cửa sổ dài $4$. Đưa thêm $4$ vào thì tổng thành $12$, vượt $T$. Đầu trái tiến lên, bỏ số $2$ ở đầu cửa sổ ra, tổng còn $10$ và không còn vượt $T$. Tiếp tục như vậy tới hết dãy, độ dài lớn nhất gặp được là $4$, cũng là đáp án của bài. Bạn có thể bấm chạy để xem từng bước, hoặc đổi dãy số và $T$ để thử:

Nếu xếp các cửa sổ sau mỗi bước chồng lên nhau, ta sẽ thấy cả hai đầu của cửa sổ đều chỉ đi sang phải.

Nhìn vòng while nằm trong vòng for, ta dễ nghĩ chương trình vẫn chạy $O(n^2)$. Tuy nhiên, nếu đếm theo từng phần tử thay vì theo từng vòng lặp, ta sẽ thấy mỗi phần tử được đưa vào cửa sổ đúng một lần, khi đầu phải đi qua, và bị bỏ ra nhiều nhất một lần, khi đầu trái đi qua. Mỗi đầu đi tối đa $n$ bước, nên cả chương trình chỉ có khoảng $2n$ bước. Cách đếm tổng số bước di chuyển của các con trỏ trên toàn chương trình như thế này còn được dùng ở nhiều bài sau.

Ví dụĐoạn Việc Trong Ngân Sách

Đề. Có $n \le 10^5$ công việc, việc $i$ cần $a_i$ đơn vị thời gian ($1 \le a_i \le 10^4$), và ngân sách $T \le 10^9$. Tìm độ dài lớn nhất của một đoạn việc liên tiếp có tổng thời gian không vượt $T$; được chọn đoạn rỗng.

Lời giải. Đây là bài toán vừa giải ở trên. Có một trường hợp cần chú ý: một việc có thời gian lớn hơn cả $T$. Khi đó vòng while bỏ hết các việc trong cửa sổ, kể cả chính việc đó, cho tới khi $l = r + 1$ và sum bằng $0$. Cửa sổ lúc này rỗng, có độ dài $0$, đúng với đoạn rỗng mà đề cho phép. Trước khi bỏ bớt việc, sum có thể lên tới $T + a_r \le 10^9 + 10^4$, vẫn vừa kiểu int; dùng long long thì không phải lo chuyện tràn số.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, t, a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> t;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    ll l = 1, sum = 0, ans = 0;
    for (ll r = 1; r <= n; r++) {
        sum += a[r];
        while (sum > t) sum -= a[l++];
        ans = max(ans, r - l + 1);
    }
    cout << ans << '\n';
}

ChạyInput7 10
6 2 3 5 1 1 4

Output4

Độ phức tạp: $O(n)$, với $n = 10^5$ cần khoảng $2 \cdot 10^5$ phép tính.

IIKhi nào dùng được cửa sổ trượt

Trước khi đi tiếp, ta thống nhất một cách gọi. Một đoạn được gọi là đoạn tốt nếu nó thỏa điều kiện mà đề bài yêu cầu. Ở bài toán mở đầu, đoạn tốt là đoạn có tổng thời gian không quá $T$; ở một bài khác, đoạn tốt có thể là đoạn có các phần tử đôi một khác nhau, hay đoạn có tổng ít nhất $S$.

Thuật toán cửa sổ trượt ở mục trước chạy đúng nhờ một tính chất của đoạn tốt: nếu bỏ bớt một số phần tử ở hai đầu của một đoạn tốt, đoạn còn lại vẫn là đoạn tốt. Ở bài mở đầu, tính chất này đúng vì mọi thời gian đều dương, bỏ bớt việc thì tổng chỉ giảm. Nhờ tính chất này, khi đầu phải $r$ tiến lên, đầu trái $l$ không bao giờ cần lùi lại (ô Chứng minh ở mục trước), và cả thuật toán chỉ tốn $O(n)$.

Vì vậy, trước khi dùng cửa sổ trượt cho một bài mới, ta cần kiểm tra xem đoạn tốt của bài đó có một trong hai tính chất sau hay không:

• Bớt đi vẫn tốt: mọi đoạn liên tiếp nằm bên trong một đoạn tốt cũng là đoạn tốt. Với tính chất này, khi cửa sổ không còn tốt, ta bỏ bớt phần tử ở đầu trái cho tới khi nó tốt trở lại; vì vậy tính chất này phù hợp với bài tìm đoạn dài nhất và bài đếm đoạn. Ví dụ: đoạn có tổng không quá $T$ (khi mọi số đều dương), đoạn có các phần tử đôi một khác nhau, đoạn có không quá $k$ giá trị khác nhau, đoạn có hiệu giữa số lớn nhất và số nhỏ nhất không quá $d$.
• Thêm vào vẫn tốt: mọi đoạn chứa một đoạn tốt cũng là đoạn tốt. Với tính chất này, khi cửa sổ đã tốt, ta thử bỏ bớt phần tử ở đầu trái để tìm đoạn ngắn hơn mà vẫn tốt; vì vậy tính chất này phù hợp với bài tìm đoạn ngắn nhất. Ví dụ: đoạn có tổng ít nhất $S$ (khi mọi số đều dương), đoạn chứa đủ mọi loại ký tự cho trước.

Sử dụng kiến thức này cũng có thể giải bài: chọn nhiều số nhất trong dãy, không cần đứng liền nhau, sao cho số lớn nhất trừ số nhỏ nhất không quá $d$. Chỉ cần sắp xếp dãy tăng dần rồi dùng cửa sổ trượt.

Cần cẩn thận khi dãy có số âm. Khi đó bỏ bớt phần tử có thể làm tổng tăng lên, nên tính chất “bớt đi vẫn tốt” thường không còn đúng, và cửa sổ trượt có thể cho kết quả sai. Chẳng hạn với dãy $5, -4, 1$ và $T = 2$: cả dãy có tổng $2$, nên đáp án là $3$. Nhưng ở bước đầu tiên, riêng số $5$ đã vượt $T$, nên thuật toán bỏ số $5$ ra khỏi cửa sổ. Đến khi gặp $-4$ thì số $5$ đã bị bỏ, không thể đưa trở lại, và thuật toán in ra $2$.

Tương tự, các điều kiện như “tổng đúng bằng $x$” hay “tổng chia hết cho $m$” thường không có hai tính chất trên. Những bài như vậy thường được giải bằng tổng tiền tố kết hợp mảng đếm (bài 0.3).

IIIBa dạng bài: dài nhất, ngắn nhất, đếm đoạn

Cửa sổ trượt thường được dùng cho ba dạng câu hỏi. Ta xét cả ba trên cùng một dãy số dương $a_1, a_2, \dots, a_n$:

1. Đoạn dài nhất: tìm đoạn liên tiếp dài nhất có tổng không quá $T$. Đây là bài toán ở đầu bài học.
2. Đoạn ngắn nhất: tìm đoạn liên tiếp ngắn nhất có tổng ít nhất $S$.
3. Đếm đoạn: đếm số đoạn liên tiếp có tổng không quá $T$.

Ví dụ với dãy $2, 3, 1, 2, 4, 3$ và $T = S = 7$: đoạn dài nhất có tổng không quá $7$ dài $3$, chẳng hạn $2, 3, 1$; đoạn ngắn nhất có tổng ít nhất $7$ dài $2$, đó là $4, 3$; và có $14$ đoạn có tổng không quá $7$.

Cả ba bài đều dùng chung một vòng lặp: đầu phải $r$ đi từ trái sang phải, mỗi bước đưa $a_r$ vào cửa sổ, rồi vòng while bỏ bớt phần tử ở đầu trái khi cần. Điểm khác nhau nằm ở chỗ cập nhật đáp án: cập nhật ở đâu và cập nhật bằng giá trị nào. Đây cũng là chỗ dễ viết sai, nên ta xem lần lượt từng bài.

Đoạn dài nhất. Đây là bài đã giải ở mục đầu. Sau khi vòng while dừng, cửa sổ $[l, r]$ có tổng không quá $T$, và đó là đoạn tốt dài nhất kết thúc tại $r$. Vì vậy ta cập nhật đáp án ngay sau vòng while.

Đoạn ngắn nhất. Lần này đoạn tốt là đoạn có tổng ít nhất $S$, và ta muốn đoạn đó càng ngắn càng tốt. Khi cửa sổ $[l, r]$ đã có tổng ít nhất $S$, ta ghi nhận độ dài của nó, rồi thử bỏ $a_l$ để xem đoạn ngắn hơn có còn đủ tổng hay không. Cần chú ý thứ tự: ghi nhận độ dài trước, rồi mới bỏ $a_l$. Khi vòng while dừng, tổng của cửa sổ đã nhỏ hơn $S$, nên độ dài lúc này không còn là một đáp án hợp lệ.

Biến ans bắt đầu từ $10^{18}$, một số rất lớn, để lần ghi nhận đầu tiên luôn nhỏ hơn nó. Nếu hết vòng lặp mà ans vẫn bằng $10^{18}$ thì dãy không có đoạn nào có tổng ít nhất $S$.

ll l = 1, sum = 0, ans = 1e18;
for (ll r = 1; r <= n; r++) {
    sum += a[r];
    while (sum >= s) {
        ans = min(ans, r - l + 1);
        sum -= a[l++];
    }
}

Độ phức tạp: $O(n)$, với $n = 10^5$ cần khoảng $2 \cdot 10^5$ phép tính.

Đếm đoạn. Xét một vị trí $r$. Sau khi vòng while dừng, đoạn $[l, r]$ có tổng không quá $T$. Các đoạn kết thúc tại $r$ và bắt đầu từ $l$ trở về sau, tức là $[l, r], [l + 1, r], \dots, [r, r]$, đều nằm trong đoạn $[l, r]$; các số đều dương nên tổng của chúng cũng không quá $T$. Còn các đoạn kết thúc tại $r$ mà bắt đầu trước $l$ thì có tổng vượt $T$, vì $l$ là đầu trái nhỏ nhất thỏa điều kiện (ô Chứng minh ở mục đầu). Như vậy, có đúng $r - l + 1$ đoạn thỏa điều kiện kết thúc tại $r$. Cộng con số này với mọi $r$, ta được số đoạn cần đếm; mỗi đoạn được đếm đúng một lần, tại vị trí kết thúc của nó.

ll l = 1, sum = 0, cnt = 0;
for (ll r = 1; r <= n; r++) {
    sum += a[r];
    while (sum > t) sum -= a[l++];
    cnt += r - l + 1;
}

Độ phức tạp: $O(n)$, với $n = 10^5$ cần khoảng $2 \cdot 10^5$ phép tính.

Với dãy $2, 3, 1, 2, 4, 3$ và $T = 7$, giá trị $r - l + 1$ ở các bước lần lượt là $1, 2, 3, 3, 3, 2$, cộng lại được $14$ đoạn.

Số đoạn có thể lên tới $\frac{n(n+1)}{2}$, khoảng $5 \cdot 10^9$ khi $n = 10^5$, vượt giới hạn của kiểu int. Vì vậy cần dùng kiểu long long cho kết quả.

Bài đếm còn hai biến thể hay gặp, chỉ cần sửa một chút:

• Đếm đoạn có tổng ít nhất $S$: dùng vòng lặp của bài đoạn ngắn nhất. Sau vòng while, mọi đoạn kết thúc tại $r$ và bắt đầu trước $l$ đều đủ tổng, còn các đoạn bắt đầu từ $l$ trở đi thì không, nên ta cộng $l - 1$ vào kết quả.
• Đếm đoạn có tổng đúng bằng $x$: lấy số đoạn có tổng không quá $x$ trừ đi số đoạn có tổng không quá $x - 1$.

IVCửa sổ nhớ thêm thông tin

Ở các bài trên, cửa sổ chỉ cần nhớ tổng các số bên trong. Bài khác có thể cần nhớ nhiều hơn, nhưng vòng lặp vẫn giữ nguyên. Ta chỉ cần cập nhật nhanh được khi thêm một số ở bên phải, khi bỏ một số ở bên trái, và biết được cửa sổ hiện tại có còn tốt hay không. Hai trường hợp hay gặp:

• Số giá trị khác nhau: đếm xem mỗi giá trị xuất hiện bao nhiêu lần trong cửa sổ. Thêm một số mà trước đó chưa có trong cửa sổ thì số giá trị khác nhau tăng 1; bỏ một số mà sau đó không còn trong cửa sổ thì giảm 1. Ví dụ ngay dưới đây làm đúng như vậy.
• Tích các số nguyên dương: thêm một số thì nhân tích với số đó, bỏ một số thì chia tích cho số đó.

Ví dụĐoạn Dài Nhất Có Không Quá K Giá Trị

Đề. Cho dãy $n$ số $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^6$) và số $k$ ($1 \le k \le n \le 5 \cdot 10^5$). In hai đầu mút của một đoạn dài nhất có không quá $k$ giá trị khác nhau; nếu có nhiều đoạn dài nhất, in đoạn nào cũng được.

Lời giải. Bỏ bớt phần tử thì số giá trị khác nhau chỉ có thể giảm, nên đoạn tốt ở bài này có tính chất “bớt đi vẫn tốt”. Cửa sổ cần nhớ số lần xuất hiện của từng giá trị và số giá trị khác nhau. Với mỗi $r$, ta thêm $a_r$ vào cửa sổ; khi số giá trị khác nhau vượt $k$, ta bỏ $a_l$ ra và tăng $l$. Sau vòng while, $[l, r]$ là đoạn tốt dài nhất kết thúc tại $r$. Ở đây ta chỉ cập nhật đáp án khi gặp đoạn dài hơn hẳn, nên chương trình in đoạn dài nhất xuất hiện đầu tiên. Vì $0 \le a_i \le 10^6$, mảng đếm cần $10^6 + 1$ ô, chỉ số từ $0$ tới $10^6$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 5e5 + 5;
ll n, k, a[N], cnt[1000005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    ll l = 1, diff = 0, bl = 1, br = 1;
    for (ll r = 1; r <= n; r++) {
        if (cnt[a[r]]++ == 0) diff++;
        while (diff > k) {
            if (--cnt[a[l]] == 0) diff--;
            l++;
        }
        if (r - l > br - bl) bl = l, br = r;
    }
    cout << bl << ' ' << br << '\n';
}

ChạyInput10 2
1 2 1 3 4 3 3 4 5 4

Output4 8

Độ phức tạp: $O(n)$, với $n = 5 \cdot 10^5$ cần khoảng $10^6$ phép tính.

VTìm cặp có tổng bằng x

Phần này trình bày dạng thứ hai của hai con trỏ. Bài toán: cho một dãy đã sắp xếp tăng dần $b_1 \le b_2 \le \dots \le b_m$ và một số $x$; tìm hai phần tử ở hai vị trí khác nhau có tổng bằng $x$.

Cách ngây thơ là thử mọi cặp phần tử. Có khoảng $\frac{m^2}{2}$ cặp, nên với $m = 2 \cdot 10^5$ ta phải thử khoảng $2 \cdot 10^{10}$ cặp, quá chậm. Hai con trỏ tận dụng việc dãy đã được sắp xếp để mỗi bước loại được một phần tử không thể thuộc cặp nào.

Ta chạy tay với dãy $1, 3, 4, 6, 8, 11, 14$ và $x = 19$. Đặt con trỏ $l$ ở số nhỏ nhất và con trỏ $r$ ở số lớn nhất:

• $1 + 14 = 15$, nhỏ hơn $19$. Số $1$ ghép với số lớn nhất còn lại mà vẫn chưa đủ, nên ghép với số nào khác cũng không đủ. Ta bỏ số $1$.
• $3 + 14 = 17$, rồi $4 + 14 = 18$, vẫn nhỏ hơn $19$. Ta bỏ tiếp $3$ và $4$.
• $6 + 14 = 20$, lớn hơn $19$. Lần này số $14$ ghép với số nhỏ nhất còn lại mà đã vượt, nên ghép với số nào khác cũng vượt. Ta bỏ số $14$.
• $6 + 11 = 17$, nhỏ hơn $19$, bỏ số $6$. Còn lại $8 + 11 = 19$: đã tìm được cặp.

Có thể tóm tắt cách làm thành ba quy tắc: nếu tổng nhỏ hơn $x$ thì bỏ số bên trái (tăng $l$); nếu tổng lớn hơn $x$ thì bỏ số bên phải (giảm $r$); nếu tổng bằng $x$ thì đã tìm được cặp. Mỗi bước loại được một số không thể thuộc cặp nào, nên với $m$ phần tử, ta cần không quá $m - 1$ bước.

Bảng bên phải trong hình ghi tổng của mọi cặp. Mỗi bước loại đi cả một hàng hoặc một cột của bảng, và đường đi của hai con trỏ bám theo ranh giới giữa vùng có tổng nhỏ hơn $x$ và vùng có tổng lớn hơn $x$:

Điều kiện của vòng lặp phải là l < r, không phải l <= r. Nếu viết <=, khi $l = r$ ta sẽ ghép một phần tử với chính nó: dãy $3, 5, 8$ với $x = 10$ sẽ báo có cặp $5 + 5$.

Ví dụHai Vị Trí Có Tổng

Đề. Cho mảng $n$ số $a_1, a_2, \dots, a_n$ và số $x$ ($n \le 2 \cdot 10^5$, $1 \le x, a_i \le 10^9$). In hai chỉ số khác nhau $i, j$ với $a_i + a_j = x$ (nhiều cặp thì in cặp nào cũng được), hoặc in IMPOSSIBLE nếu không có.

Lời giải. Mảng chưa được sắp xếp, nhưng đề lại yêu cầu in vị trí ban đầu. Vì vậy ta lưu mỗi số cùng vị trí của nó thành một cặp (giá trị, vị trí), sắp xếp các cặp theo giá trị, chạy hai con trỏ trên giá trị rồi in ra vị trí ban đầu. Vì luôn có $l < r$, hai vị trí in ra luôn khác nhau, kể cả khi hai giá trị bằng nhau. Tổng hai số có thể lên tới $2 \cdot 10^9$, vượt giới hạn của int, nên ta dùng long long.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, x;
pair<ll, ll> a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);
    ll l = 1, r = n;
    while (l < r) {
        ll s = a[l].first + a[r].first;
        if (s == x) {
            cout << a[l].second << ' ' << a[r].second << '\n';
            return 0;
        }
        if (s < x) l++;
        else r--;
    }
    cout << "IMPOSSIBLE\n";
}

ChạyInput6 13
8 2 11 5 7 1

Output2 3

Độ phức tạp: $O(n \log n)$ cho bước sắp xếp, phần hai con trỏ chỉ $O(n)$; với $n = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^6$ phép tính.

Sử dụng kiến thức này cũng có thể giải bài: tìm ba số có tổng bằng $x$. Sau khi sắp xếp, cố định số nhỏ nhất của bộ ba rồi tìm hai số còn lại bằng hai con trỏ như trên; cả bài tốn $O(n^2)$.

VIĐếm cặp có tổng không quá X

Bài toán: cho dãy $n$ số, đếm số cặp vị trí $i < j$ có $a_i + a_j \le X$. Thứ tự ban đầu của dãy không ảnh hưởng tới số cặp, nên ta có thể sắp xếp dãy tăng dần, rồi đặt $l = 1$, $r = n$:

• Nếu $a_l + a_r \le X$: số $a_l$ ghép với số lớn nhất còn lại là $a_r$ mà tổng vẫn không vượt $X$, nên ghép với mọi số $a_{l+1}, \dots, a_{r-1}$ đứng giữa (đều nhỏ hơn hoặc bằng $a_r$) cũng không vượt. Có tất cả $r - l$ cặp như vậy, đều chứa $a_l$. Ta cộng $r - l$ vào kết quả rồi bỏ $a_l$ (tăng $l$), vì mọi cặp chứa $a_l$ đã được đếm.
• Nếu $a_l + a_r > X$: số $a_r$ ghép với số nhỏ nhất còn lại là $a_l$ mà tổng đã vượt $X$, nên ghép với số nào khác cũng vượt; $a_r$ không thuộc cặp nào thỏa điều kiện. Ta bỏ $a_r$ (giảm $r$).

Muốn đếm số cặp có tổng nằm trong khoảng $[L, R]$, ta lấy số cặp có tổng không quá $R$ trừ đi số cặp có tổng không quá $L - 1$, giống cách đếm đoạn có tổng đúng bằng $x$ ở mục trước.

Ví dụĐếm Cặp Có Tổng Trong Khoảng

Đề. Có nhiều bộ dữ liệu. Mỗi bộ gồm dãy $n$ số nguyên dương và hai số $L \le R$; đếm số cặp chỉ số $i < j$ với $L \le a_i + a_j \le R$. Tổng $n$ qua các bộ dữ liệu không quá $2 \cdot 10^5$.

Lời giải. Gọi $F(X)$ là số cặp có tổng không quá $X$, tính bằng hai con trỏ như trên. Sắp xếp dãy, đáp án là $F(R) - F(L - 1)$. Số cặp có thể tới $2 \cdot 10^{10}$, nên cần dùng kiểu long long cho kết quả.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll t, n, lo, hi, a[N];

ll f(ll x) {
    ll l = 1, r = n, cnt = 0;
    while (l < r) {
        if (a[l] + a[r] <= x) {
            cnt += r - l;
            l++;
        } else r--;
    }
    return cnt;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> lo >> hi;
        for (ll i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1);
        cout << f(hi) - f(lo - 1) << '\n';
    }
}

ChạyInput3
5 6 10
1 1 5 6 9
4 8 8
4 4 4 4
6 2 20
1 2 3 4 5 6

Output6
6
15

Độ phức tạp: $O(n \log n)$ cho mỗi test vì phải sắp xếp, hai lần đếm chỉ thêm $O(n)$; tổng $n$ không quá $2 \cdot 10^5$ nên cần khoảng $4 \cdot 10^6$ phép tính.

VIIHai con trỏ trên hai dãy

Hai con trỏ cũng dùng được khi có hai dãy cùng được sắp xếp tăng dần: mỗi dãy có một con trỏ riêng, và ở mỗi bước ta chỉ tiến con trỏ của dãy cần tiến. Ví dụ quen thuộc nhất là bước trộn của sắp xếp trộn (bài 0.4): so sánh hai số đang đứng đầu ở hai dãy, lấy số nhỏ hơn đưa vào kết quả, rồi tiến con trỏ của dãy chứa số đó. Các bài tìm phần tử chung, lấy hợp hay hiệu của hai dãy cũng làm theo cách tương tự.

Một cách dùng khác: ta cần trả lời nhiều câu hỏi trên một dãy, và các câu hỏi được xét theo thứ tự tăng dần. Khi đó, thay vì tìm kiếm nhị phân (bài 0.6) riêng cho từng câu hỏi, con trỏ chỉ cần tiến tiếp từ vị trí của câu hỏi trước. Ví dụ: cho hai dãy đã sắp xếp tăng dần, dãy $a$ có $n$ số và dãy $b$ có $m$ số; với mỗi $a_i$, đếm số phần tử của $b$ nhỏ hơn $a_i$. Con trỏ $j$ dừng tại phần tử đầu tiên của $b$ không nhỏ hơn $a_i$, nên có $j - 1$ phần tử nhỏ hơn. Vì $a$ tăng dần, vị trí dừng cho $a_{i+1}$ không thể đứng trước vị trí dừng cho $a_i$, nên $j$ chỉ cần tiến tiếp:

ll j = 1;
for (ll i = 1; i <= n; i++) {
    while (j <= m && b[j] < a[i]) j++;
    cnt[i] = j - 1;
}

Độ phức tạp: $O(n + m)$, với $n = m = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^5$ phép tính.

Kiểm tra dãy con. Cho hai chuỗi $s$ và $t$. Hỏi $t$ có phải dãy con của $s$ không, tức là có thể xóa bớt một số ký tự của $s$ (giữ nguyên thứ tự những ký tự còn lại) để được $t$ hay không. Ta duyệt $s$ từ trái sang phải, đồng thời giữ con trỏ $j$ trên $t$ (chỉ số ký tự của $t$ đang cần tìm); mỗi khi gặp ký tự bằng $t_j$ thì tiến $j$. Nếu duyệt hết $s$ mà $j$ đã đi hết $t$ thì $t$ là dãy con của $s$.

ll n = s.size(), m = t.size(), j = 0;
for (ll i = 0; i < n && j < m; i++)
    if (s[i] == t[j]) j++;
cout << (j == m ? "YES" : "NO") << '\n';

Độ phức tạp: $O(|s|)$, với chuỗi $s$ dài $10^6$ cần khoảng $10^6$ phép tính.

Ví dụGhép Kích Thước

Đề. Có $n$ yêu cầu với kích thước $a_1, \dots, a_n$ và $m$ tài nguyên với kích thước $b_1, \dots, b_m$ ($n, m \le 2 \cdot 10^5$, các kích thước và $k$ không quá $10^9$). Yêu cầu kích thước $x$ ghép được với tài nguyên kích thước $y$ khi $|x - y| \le k$; mỗi yêu cầu và mỗi tài nguyên dùng trong nhiều nhất một cặp. Tìm số cặp lớn nhất có thể tạo.

Lời giải. Sắp xếp cả hai dãy, con trỏ $i$ chạy trên dãy yêu cầu, con trỏ $j$ chạy trên dãy tài nguyên. Ở mỗi bước có ba khả năng:

• Tài nguyên quá nhỏ ($b_j < a_i - k$): các yêu cầu sau chỉ lớn hơn, nên tài nguyên này không ghép được với yêu cầu nào nữa. Ta bỏ tài nguyên này.
• Tài nguyên quá lớn ($b_j > a_i + k$): các tài nguyên sau chỉ lớn hơn, nên yêu cầu này không ghép được với tài nguyên nào nữa. Ta bỏ yêu cầu này.
• Ghép được: ta ghép yêu cầu $i$ với tài nguyên $j$ ngay, rồi tiến cả hai con trỏ.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, m, k, a[N], b[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll j = 1; j <= m; j++) cin >> b[j];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    ll i = 1, j = 1, ans = 0;
    while (i <= n && j <= m) {
        if (b[j] < a[i] - k) j++;
        else if (b[j] > a[i] + k) i++;
        else ans++, i++, j++;
    }
    cout << ans << '\n';
}

ChạyInput6 5 3
30 41 44 50 65 70
28 39 46 67 80

Output4

Độ phức tạp: $O(n \log n + m \log m)$ cho bước sắp xếp, phần ghép chỉ $O(n + m)$ vì mỗi bước tiến ít nhất một con trỏ; với $n = m = 2 \cdot 10^5$ cần khoảng $7 \cdot 10^6$ phép tính.