Two Pointers

Cửa sổ trượt

Đánh số từ 1, đoạn đóng $[l, r]$; đoạn rỗng viết là $l = r + 1$. Cố định đầu phải $r$. Mọi $a_i$ dương nên khi $l$ tăng, tổng đoạn $[l, r]$ giảm, vì thế các đầu trái cho tổng không vượt $T$ nằm liền nhau ở phía phải. Gọi $L(r)$ là đầu trái nhỏ nhất thỏa; đoạn dài nhất kết thúc tại $r$ là $[L(r), r]$. Điều làm nên kỹ thuật là $L(r)$ không bao giờ lùi:

vì bỏ $a_{r+1} > 0$ khỏi đoạn $[L(r+1), r+1]$ cho đoạn $[L(r+1), r]$ có tổng nhỏ hơn, vẫn thỏa. Vậy chỉ cần một biến $l$: sang bước $r$, xuất phát từ $l$ cũ rồi đẩy sang phải cho tới khi đoạn thỏa; mọi đầu trái đã vượt qua bị loại vĩnh viễn. Giữ thêm sum là tổng cửa sổ: thêm $a_r$ thì cộng, bỏ $a_l$ thì trừ.

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);
}

Vòng while nằm trong vòng for làm ta ngờ là $O(n^2)$, nhưng phải đếm tổng thể. Mỗi lần thân while chạy thì l tăng 1, mà l chỉ tăng và không vượt $n + 1$, nên qua cả chương trình thân while chạy không quá $n$ lần. Mỗi phần tử vào cửa sổ một lần và ra không quá một lần: tổng cộng không quá $2n$ thao tác. Cách đếm này nhìn tổng số bước của con trỏ trên cả chương trình thay vì từng vòng, và sẽ dùng lại ở nhiều bài sau.

Lập luận chỉ dùng một tính chất của đề: bỏ bớt phần tử khỏi một đoạn thỏa thì đoạn còn lại vẫn thỏa. Gọi đoạn thỏa là tốt. Cửa sổ trượt dùng được khi “tốt” đơn điệu theo một trong hai chiều:

• Loại A: đoạn con của đoạn tốt vẫn tốt. Dùng cho “dài nhất” và “đếm”. Ví dụ: tổng $\le T$ với số dương; các phần tử đôi một khác nhau; không quá $k$ giá trị khác nhau; $\max - \min \le d$.
• Loại B: đoạn chứa một đoạn tốt vẫn tốt. Dùng cho “ngắn nhất”. Ví dụ: tổng $\ge S$ với số dương; chứa đủ mọi loại ký tự.

Số âm là chỗ dễ bị lừa. Với $a = (5, -4, 1)$ và $T = 2$, cả dãy có tổng 2 nên đáp án là 3. Chương trình trên bỏ $a_1$ ở $r = 1$ vì $5 > 2$; sau đó $a_2 = -4$ kéo tổng xuống, đoạn chứa $a_1$ lại tốt, nhưng $a_1$ đã bị loại. Nó in 2. Các điều kiện “tổng đúng bằng $x$” khi có số âm, “tổng chia hết cho $m$” cũng không đơn điệu; chúng giải bằng tổng tiền tố và bảng đếm (bài 02).

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

Đề. $n \le 10^5$ công việc, việc $i$ cần $a_i$ đơn vị thời gian. Chọn một đoạn liên tiếp (có thể rỗng) có tổng không vượt $T$, dài nhất.

Lời giải. Đúng mẫu ở trên: tổng $\le T$ với số dương là điều kiện loại A. Khi một mình $a_r > T$, vòng while bỏ cả $a_r$ tới khi $l = r + 1$ và sum bằng 0, ghi nhận độ dài 0 đúng với đoạn rỗng. sum không vượt $T + 10^4$ nhưng cứ dùng long long.

#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

Dài nhất, ngắn nhất, đếm

Dài nhất (loại A) là bài vừa làm: co mép trái cho tới khi cửa sổ tốt, rồi ghi nhận $r - l + 1$ sau vòng co.

Ngắn nhất (loại B), ví dụ đoạn ngắn nhất có tổng $\ge S$ trên dãy dương. Với $r$ cố định, đoạn ngắn nhất kết thúc tại $r$ dùng đầu trái lớn nhất còn tốt. Ta vẫn co từ trái, nhưng trong khi đoạn còn tốt: ghi nhận độ dài rồi mới bỏ $a_l$. Khi thoát vòng, đoạn đã hỏng vì vừa bỏ quá tay một phần tử, nên không được ghi nhận.

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

Đếm đoạn tốt. Với loại A, mọi đầu trái từ $l$ (sau vòng co) đến $r$ đều cho đoạn tốt, nên cộng $r - l + 1$. Với loại B, mọi đầu trái đã bị bỏ đều tốt còn $l$ thì không, nên cộng $l - 1$. Đáp án tới $\frac{n(n+1)}{2}$, đếm bằng long long. Đếm đoạn có tổng đúng bằng $x$ trên dãy dương thì với mỗi $r$ chỉ có tối đa một đầu trái, hoặc lấy hiệu: số đoạn có tổng $\le x$ trừ số đoạn có tổng $\le x - 1$.

Trạng thái cửa sổ

Cửa sổ trượt thật ra cần một cấu trúc nhớ nội dung cửa sổ, với ba thao tác: thêm phần tử bên phải, bỏ phần tử bên trái, và trả lời “đoạn hiện tại còn tốt không”. Với tổng, đó là một biến. Các trạng thái hay gặp khác:

• Tích của số nguyên dương: một biến prod, bỏ phần tử bằng prod /= a[l]. Có số 0 thì phép chia hỏng, phải xử lý riêng.
• Số giá trị khác nhau: mảng đếm cnt[v] và biến diff. Thêm $v$: if (cnt[v]++ == 0) diff++. Bỏ $v$: if (--cnt[v] == 0) diff--. Giá trị lớn thì nén tọa độ (bài 03).
• Hiệu lớn nhất trừ nhỏ nhất: cần cực trị của cửa sổ, dùng multiset (bài 09, $O(\log n)$ mỗi thao tác) hoặc hàng đợi đơn điệu.

Hàng đợi đơn điệu cho giá trị lớn nhất giữ một deque (hàng đợi hai đầu, thêm bớt được ở cả đầu lẫn đuôi; bài 09) các chỉ số trong cửa sổ với giá trị giảm ngặt từ đầu về đuôi. Thêm $r$: bỏ mọi chỉ số ở đuôi có giá trị $\le a_r$, vì chúng đứng trước $r$ mà không lớn hơn, cửa sổ nào còn chứa chúng cũng chứa $r$. Rồi $r$ vào đuôi. Giá trị lớn nhất của cửa sổ là phần tử đầu; khi mép trái vượt qua chỉ số ở đầu thì bỏ đầu. Mỗi chỉ số vào một lần, ra một lần: $O(n)$.

while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
mx.push_back(r);
while (mx.front() < l) mx.pop_front();

multiset cũng cho giá trị lớn nhất của cửa sổ, viết nhanh hơn, nhưng mỗi bước tốn $O(\log k)$ cùng một lần cấp phát nút:

Hàng đợi đơn điệu nhanh hơn khoảng 20 lần. Với $n = 2 \cdot 10^5$ thì multiset vẫn qua; khi $n$ tới $10^6$ hoặc phải chạy nhiều lần, hãy dùng deque.

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

Đề. Dãy $n \le 5 \cdot 10^5$ số, $0 \le a_i \le 10^6$, và số $k$. 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.

Lời giải. Đoạn con của đoạn có không quá $k$ giá trị cũng vậy, nên điều kiện thuộc loại A. Giữ cnt và diff; với mỗi $r$, thêm $a_r$, trong khi diff > k thì bỏ $a_l$. Sau vòng co $[l, r]$ là đoạn tốt dài nhất kết thúc tại $r$; cập nhật đáp án khi dài hơn hẳn, nên in ra đoạn dài nhất xuất hiện đầu tiên. Mỗi phần tử vào ra một lần, $O(n)$; mảng đếm $10^6 + 1$ ô.

#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

Cặp có tổng cho trước

Bài toán: cho $b_1 \le b_2 \le \dots \le b_m$ đã sắp và số $x$; tìm $i < j$ với $b_i + b_j = x$. Thử mọi cặp là $O(m^2)$, chặt nhị phân cho từng $b_i$ là $O(m \log m)$; hai con trỏ làm trong $O(m)$. Đặt $l = 1$, $r = m$, xét $s = b_l + b_r$:

• $s = x$: xong.
• $s < x$: $b_r$ là số lớn nhất còn lại mà ghép với $b_l$ vẫn thiếu, nên $b_l$ ghép với số nào còn lại cũng nhỏ hơn $x$. Loại $b_l$.
• $s > x$: $b_l$ là số nhỏ nhất còn lại mà ghép với $b_r$ vẫn thừa, nên loại $b_r$.

Bất biến: nếu có cặp $(i, j)$ với tổng $x$ thì $l \le i < j \le r$. Mỗi bước chỉ loại một phần tử đã được chứng minh không thuộc cặp nào còn lại, và $r - l$ giảm 1, nên vòng dừng sau không quá $m - 1$ bước.

Có thể nhìn bằng bảng các cặp: ô $(i, j)$ chứa $b_i + b_j$, tăng khi đi sang phải và đi lên. Mỗi bước gạch bỏ cả một cột hoặc một hàng, và đường đi bám sát ranh giới giữa vùng “nhỏ hơn $x$” và vùng “lớn hơn $x$”.

Điều kiện vòng lặp phải là l < r chứ không phải l <= r: để <= thì khi $l = r$ ta ghép một phần tử với chính nó, và 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

Đề. Mảng $n \le 2 \cdot 10^5$ số và số $x$. In hai chỉ số khác nhau $i, j$ với $a_i + a_j = x$, hoặc IMPOSSIBLE.

Lời giải. Mảng chưa sắp mà đề đòi vị trí ban đầu, nên sắp các cặp (giá trị, vị trí) theo giá trị, chạy hai con trỏ trên giá trị rồi in vị trí gốc. Vì $l < r$ nên hai vị trí in ra khác nhau, kể cả khi hai giá trị trùng nhau. Cả bài $O(n \log n)$.

#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

Đếm cặp

Đếm số cặp $i < j$ có $a_i + a_j \le X$. Cặp là tập hai vị trí nên thứ tự ban đầu không quan trọng, ta sắp tăng trước. Với $l = 1$, $r = n$:

• $a_l + a_r \le X$: với mọi $j$ có $l < j \le r$ ta có $a_l + a_j \le a_l + a_r \le X$, nên có đúng $r - l$ cặp $(l, j)$. Cộng $r - l$ rồi tăng $l$.
• $a_l + a_r > X$: $a_r$ ghép với mọi phần tử còn lại đều vượt $X$. Giảm $r$.

Gọi $F(X)$ là số cặp có tổng $\le X$. Với số nguyên, số cặp có tổng trong $[L, R]$ là $F(R) - F(L - 1)$: cùng mẹo hiệu hai lần đếm ở mục đếm đoạn.

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

Đề. Dãy $n$ số nguyên dương và hai số $L \le R$; đếm cặp $i < j$ với $L \le a_i + a_j \le R$. Tổng $n$ qua các test không quá $2 \cdot 10^5$.

Lời giải. Sắp dãy, đáp án là $F(R) - F(L - 1)$ với $F$ tính bằng hai con trỏ như trên. Số cặp tới $2 \cdot 10^{10}$, dùng long long.

#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

Hai dãy, hai con trỏ

Với hai dãy cùng sắp tăng ta dùng một con trỏ cho mỗi dãy và chỉ đẩy con trỏ cần tiến: trộn hai dãy (như bước trộn của sắp xếp trộn, bài 03), tìm giá trị chung, hợp, hiệu. Cũng dạng đó là khi các câu hỏi cho theo thứ tự tăng: thay cho một lần chặt nhị phân mỗi câu, con trỏ trên dãy kia chỉ tiến. Ví dụ đếm, với mỗi $a_i$, số phần tử của $b$ nhỏ hơn nó:

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

Khớp dãy con. Kiểm chuỗi $t$ có là dãy con của chuỗi $s$ không: duyệt $s$, mỗi khi ký tự của $s$ bằng ký tự đang cần của $t$ thì tiến con trỏ trên $t$. Tham lam này đúng vì dời mỗi ký tự được ghép về lần xuất hiện sớm nhất còn dùng được chỉ để lại nhiều chỗ hơn cho các ký tự sau.

Còn một dạng nữa là hai con trỏ cùng chiều nhưng khác tốc độ: trên dãy $x_{i+1} = f(x_i)$, con trỏ chậm đi một bước, con trỏ nhanh đi hai bước; nếu có chu kỳ thì hai con trỏ gặp nhau trong chu kỳ, chỉ tốn $O(1)$ bộ nhớ. Đó là thuật toán thỏ và rùa của Floyd.

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

Đề. $n$ yêu cầu kích thước $a_i$ và $m$ tài nguyên kích thước $b_j$ ($n, m \le 2 \cdot 10^5$). Ghép yêu cầu $x$ với tài nguyên $y$ được khi $|x - y| \le k$, mỗi bên dùng nhiều nhất một lần. Tạo nhiều cặp nhất.

Lời giải. Sắp cả hai dãy, con trỏ $i$ trên yêu cầu, $j$ trên tài nguyên. Tài nguyên quá nhỏ ($b_j < a_i - k$) thì không ghép được với yêu cầu nào từ $i$ trở đi (các yêu cầu sau chỉ lớn hơn), bỏ nó. Tài nguyên quá lớn ($b_j > a_i + k$) thì yêu cầu $a_i$ không ghép được với tài nguyên nào từ $j$ trở đi, bỏ yêu cầu. Vừa thì ghép ngay: lập luận đổi chỗ cho thấy ghép yêu cầu nhỏ nhất với tài nguyên nhỏ nhất còn dùng được không bao giờ làm mất cặp. Cả bài $O(n \log n + m \log m)$.

#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