---
title
Hai con trỏ - Bài tập và lời giải
---

Hai con trỏ - Bài tập và lời giải
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

## Bài 1: [CSES - Sum of Two Values](https://cses.fi/problemset/task/1640)

#### Tóm tắt

- Cho mảng $a$ gồm $n$ phần tử. Tìm hai vị trí $i$ và $j$ sao cho $a_i + a_j = x$.

#### Input

- Dòng đầu gồm 2 số nguyên dương $n$ và $x$.
- Dòng thứ hai gồm $n$ số nguyên dương $a_1, a_2, ..., a_n$.

#### Output

- In ra hai số nguyên dương là vị trí $i$ và $j$ cần tìm. Nếu có nhiều đáp án thì in đáp án bất kì. Nếu không có đáp án thì in `IMPOSSIBLE`.

#### Giới hạn

- $1 \le n \le 2\cdot10^5$
- $1 \le x, a_i \le 10^9$

#### Sample Input

4 8
2 7 5 1

#### Sample Output

2 4

#### Lời giải
::: spoiler Ý tưởng
- Giả sử mảng $a$ không giảm: Khi xét hai số $a_l$ và $a_r$ trong mảng, ta có nhận xét rằng tổng hai phần tử sẽ tăng khi $l$ tăng hoặc $r$ tăng.


- Từ nhận xét đó, ta có thể áp dụng kĩ thuật Hai con trỏ để cài đặt tối ưu bài toán như sau: Duy trì 2 con trỏ chạy ngược chiều nhau trong vòng lặp, xét từng vị trí $l$: Thực hiện giảm biến $r$ cho đến khi $a_l + a_r <= x$. Nếu hai con trỏ chạm vào nhau ($l >= r$), ta kết thúc vòng lặp (Vì các vị trí $l > r$ đã được kiểm tra trước đó, còn $l = r$ chắc chắn không phải đáp án của bài toán). Còn không thì kiểm tra nếu $a_l + a_r = x$ thì ta tìm được đáp án của bài toán. Nếu vòng lặp kết thúc mà ta chưa tìm thấy kết quả thì đồng nghĩa bài toán không có kết quả, in `IMPOSSIBLE`.
- Tuy nhiên, với mảng $a$ có thứ tự bất kì: Ta vẫn thực hiện sắp xếp mảng $a$ không giảm để áp dụng hai con trỏ, nhưng cần lưu thêm một giá trị là vị trí ban đầu trước khi sắp xếp của các phần tử để in đáp án. Ta có thể sử dụng CTDL `std::pair<int,int>` để làm điều này.
:::

::: spoiler Cài đặt

#include <bits/stdc++.h>

using namespace std;

pair<int, int> a[200001];

int main()
{
    int n, x;
    cin >> n >> x;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + 1 + n);
    for(int l = 1, r = n; l <= r; ++l)
    {
        while(l < r && a[l].first + a[r].first > x) --r;
        if(l == r) break;
        if(a[l].first + a[r].first == x)
        {
            cout << a[l].second << " " << a[r].second << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
}

:::

## Bài 2: [Tuyển sinh 10 Phổ Thông Năng Khiếu 2023 - Marble](https://gdoj.eu.org/problem/ptnk_marble)

#### Tóm tắt

Cho mảng $A$ gồm $N$ phần tử và mảng $B$ gồm $M$ phần tử. Hãy tìm độ dài lớn nhất của mảng được ghép bởi mảng tiền tố của $A$ và hậu tố của mảng $B$ sao cho mảng đó không giảm. Hay nói cách khác là tạo ra một dãy không giảm dài nhất: $A_1 \le A_2 \le ... \le A_i \le B_j \le B_{j + 1} \le ... \le B_M$

#### Input

- Dòng đầu tiên ghi số nguyên dương $N$.
- Dòng thứ hai ghi $N$ số nguyên: $A_1, A_2, ..., A_N$.
- Dòng thứ ba ghi số nguyên dương $M$.
- Dòng cuối cùng ghi $M$ số nguyên: $B_1, B_2, ..., B_M$.

Giá trị các phần tử của mảng $A$ và $B$ là số nguyên nằm trong khoảng $[-10^9, 10^9]$.

#### Output

Gồm $1$ dòng ghi số nguyên là kích thước lớn nhất trong các dãy tìm được.

#### Giới hạn

- $1 \le N, M \le 10^5$
- $-10^9 \le A_i, B_j \le 10^9$

#### Sample Input

3
1 4 9
4
5 2 4 5

#### Sample Output

4

#### Lời giải

:::spoiler Ý tưởng
- Nhận thấy rằng chúng ta chỉ cần quan tâm đến tiền tố dài nhất tăng dần của mảng $A$ và hậu tố dài nhất tăng dần của mảng $B$. Để đơn giản, gọi tiền tố dài nhất tăng dần của mảng $A$ là $posA$ và hậu tố dài nhất tăng dần của mảng $B$ là $posB$.
- Ta cố định vị trí tiền tố tăng dần của mảng $A$ là $i$ $(1 \le i \le posA)$. Như vậy, theo đề bài yêu cầu, ta cần tìm một vị trí $j$ $(posB \le j \le M)$ sao cho $A_i \le B_j$. Từ đó ta chỉ cần kết hợp độ dài của 2 đoạn $[1, i]$ và $[j, M]$ để được độ dài của dãy thoả mãn và tìm độ dài lớn nhất.
- Quay trở lại bài toán làm sao để tìm vị trí $j$ sao cho $A_i \le B_j$. Ta nhận thấy rằng $i$ càng tăng thì $A_i$ càng tăng $\Rightarrow$ $B_j$ càng tăng (để thoả mãn $A_i \le B_j$) $\Rightarrow$ $j$ càng tăng. Từ nhận xét này ta có thể áp dụng 2 con trỏ để xử lí.
:::
:::spoiler Cài đặt

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

int a[100005], b[100005];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    // Đọc file
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int m; cin >> m;
    for (int i = 1; i <= m; i++) cin >> b[i];
    
    // Tìm tiền tố không giảm dài nhất của mảng A và hậu tố không giảm dài nhất của mảng B
    int posA = n;
    for (int i = 1; i < n; i++)
    {
        if (a[i] > a[i + 1])
        {
            posA = i;
            break;
        }
    }
    int posB = 1;
    for (int i = m; i > 1; i--)
    {
        if (b[i] < b[i-1])
        {
            posB = i;
            break;
        }
    }
    
    // Áp dụng 2 con trỏ để tìm A[i] <= B[j]
    int j = posB;
    bool ok = 0; // Check trường hợp nếu như không tìm được bất cứ vị trí j nào sao cho A[i] <= B[j]
    int ans = 0;
    for (int i = 1; i <= posA; i++)
    {
        while (a[i] > b[j])
        {
            j++;
            if (j > m)
            {
                ok = 1;
                break;
            }
        }
        if (ok) break;
        ans = max(ans, i + m - j + 1);
    }
    cout << ans;
    
    return 0;
}

:::

## Bài 3: [CSES - Sum of Three Values](https://cses.fi/problemset/task/1641)

#### Tóm tắt

- Cho mảng $a$ gồm $n$ phần tử. Tìm ba vị trí $i, j, k$ sao cho $a_i + a_j + a_k = x$.

#### Input

- Dòng đầu gồm 2 số nguyên dương $n$ và $x$.
- Dòng thứ hai gồm $n$ số nguyên dương $a_1, a_2, ..., a_n$.

#### Output

- In ra ba số nguyên dương là vị trí $i, j, k$ cần tìm. Nếu có nhiều đáp án thì in đáp án bất kì. Nếu không có đáp án thì in `IMPOSSIBLE`.

#### Giới hạn

- $1 \le n \le 5000$
- $1 \le x, a_i \le 10^9$

#### Sample Input

4 8
2 7 5 1

#### Sample Output

1 3 4

#### Lời giải
::: spoiler Ý tưởng
- Tương tự như bài 1, ta sẽ sắp xếp mảng theo thứ tự không giảm để có thể sử dụng kĩ thuật hai con trỏ trên mảng này.
- Xét từng vị trí $i$: Ta chỉ cần tìm cặp số còn lại trong đoạn $[i+1..n]$, vì nếu tồn tại một vị trí thỏa đề thuộc đoạn $[1..i-1]$ thì đã được xét tại đó và $a_i$ là một trong hai số trong cặp số cần tìm. Từ đó, ta có thể áp dụng hai con trỏ trên đoạn $[i+1..n]$ để tìm ra hai số còn lại. Phần áp dụng hai con trỏ tương tự bài 1, nhưng chỉ trong đoạn cần xét và có $x' = x - a_i$.


:::
::: spoiler Cài đặt

#include <bits/stdc++.h>

using namespace std;

pair<int, int> a[5001];

int main()
{
    int n, x;
    cin >> n >> x;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; ++i)
    {
        for(int l = i + 1, r = n; l <= r; ++l)
        {
            while(l < r && a[i].first + a[l].first + a[r].first > x) --r;
            if(l == r) break;
            if(a[i].first + a[l].first + a[r].first == x)
            {
                cout << a[i].second << " " << a[l].second << " " << a[r].second << endl;
                return 0;
            }
        }
    }
    cout << "IMPOSSIBLE" << endl;
}

:::

## Bài 4: [VNOJ - Khai bút đầu xuân](https://oj.vnoi.info/problem/sopenp)

#### Tóm tắt

- Cho dãy số $a$ có $n$ nguyên dương. Tính xem có bao nhiêu dãy con gồm các phần tử liên tiếp của nó mà có số lượng phần tử khác nhau nằm trong đoạn $[l, r]$.

#### Input

- Dòng đầu tiên chứa các số nguyên dương $n, l, r$.
- Dòng thứ $i$ trong $n$ dòng tiếp theo là phần tử $a_i$ của dãy số $a$ ($i = 1, 2, ..., n$).

#### Output

- Một số nguyên dương là số dãy con có số lượng phần tử khác nhau nằm trong đoạn $[l, r]$.

#### Giới hạn

- $1 \le l \le r \le n \le 2^{20}$
- $1 \le a_i \le 2^{31}-1$

#### Sample Input

4 1 2
231
19
7
19

#### Sample Output

8

#### Lời giải

::: spoiler Ý tưởng
Trước hết, ta cần giải bài toán sau: Đếm số dãy con có số lượng phần tử khác nhau không quá $k$. Bài toán này có thể giải quyết như sau:
- Đầu tiên, ta cần một cấu trúc dữ liệu với các truy vấn như sau:
- `c(x)`: Số phần tử $a_i = x$ trong đoạn ta đang xét.
- `size_c()`: Số lượng `x` có `c(x)` $\ne 0$.
- `add(x)`: Hàm thêm 1 giá trị `x` vào cấu trúc dữ liệu.
- `remove(x):` Hàm xóa 1 giá trị `x` ra khỏi cấu trúc dữ liệu.
- Trong C++, ta có một cấu trúc dữ liệu đáp ứng đầy đủ yêu cầu cần thiết của cấu trúc dữ liệu này là `std::map` với độ phức tạp tất cả truy vấn $O(\log{n})$, riêng truy vấn `size_c()` còn có thể thực hiện trong $O(1)$.
- Đây là dạng bài liên quan đến đoạn tịnh tiến, trong đó điều kiện chính là `size_c()` $<= k$. Từ đó ta có thể cài đặt được bài toán (xem thêm ở phần cài đặt).

Gọi hàm trả về đáp án của bài toán trên là `calc(x)`, ta có:
- Các dãy đã được đếm trong `calc(r)` là các dãy có số lượng phần tử riêng biệt trong khoảng $[1..r]$.
- Ta cần loại đi các dãy bị đếm dư, đó chính là các dãy có số lượng phần tử riêng biệt trong khoảng $[1..l-1]$, đó cũng chính là `calc(l-1)`.
- Từ đó, ta có đáp án của bài toán là `calc(r) - calc(l - 1)`.

:::
::: spoiler Cài đặt

#include <bits/stdc++.h>

using namespace std;

int n, l, r;
int a[1048577]; // 2^20 + 1 = 1048577

// Hàm tính số dãy con có số lượng phần tử khác nhau không quá $k$:
long long calc(int k)
{
    long long ans = 0;
    map<int, int> m;
    for(int l = 1, r = 1; r <= n; ++r)
    {
        ++m[a[r]];
        while(l <= r && m.size() > k)
        {
            --m[a[l]];
            if(m[a[l]]==0) m.erase(a[l]);
            l++;
        }
        ans += r - l + 1;
    }
    return ans;
}

int main()
{
    cin >> n >> l >> r;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    cout << calc(r) - calc(l - 1) << endl;
}

:::