### Nguồn gốc
Bài này là bài cuối cùng trong [đề thi học sinh giỏi thành phố Hà Nội lớp 9 năm học 2022 - 2023](https://www.chuyentin.pro/2023/01/e-thi-hoc-sinh-gioi-lop-9-mon-tin-hoc.html)
### Quy ước:
- $\max(l, r)$ là
- Phần tử lớn nhất trong đoạn từ $l$ đến $r$.
- Với những phần tử bằng nhau thì chọn phần tử có vị trí lớn nhất
- $\min(l, r)$ là
- Phần tử nhỏ nhất trong đoạn từ $l$ đến $r$
- Với những phần tử bằng nhau thì chọn phần tử có vị trí nhỏ nhất
### Nhận xét
Một mảng con $A[l, r]$ là mảng đẹp khi và chỉ khi:
1. $\max(l, r) - \min(l, r) = r - l$
2. Không tồn tại hai phần tử nào giống nhau
Phần chứng minh xin nhường lại cho bạn đọc 😄👌
### Subtask 1 ($30/100$ số điểm): $n \le 200$
- Ta duyệt các cặp $(i, j)$
- Sau đó ta duyệt các phần tử từ $i$ đến $j$
- Ghi nhận giá trị $\max(l, r)$, $\min(l, r)$
- Kiểm tra xem có phần tử nào lặp lại nhiều lần không
- Nếu mảng con đó hợp lệ thì ta ghi nhận
### Subtask 2 ($30/100$ số điểm): $n \le 2000$ và các phần tử của $A$ phân biệt đôi một
- Ta vẫn duyệt các cặp $(i, j)$
- Nhưng để kiểm tra tính hợp lệ của mảng nhanh hơn ta dùng Segment Tree để tìm giá trị max và min trong $O(\log n)$
- Do các phần tử đôi một phân biệt nên ta không cần quan tâm đến điều kiện thứ hai nữa
### Subtask 3 ($20/100$ số điểm): $n \le 10^5$ và các phần tử của $A$ phân biệt đôi một
#### Ý tưởng
- Bình thường thì chúng ta sẽ nghĩ đến những thuật toán như hai con trỏ hay chặt nhị phân rồi tính toán gì đó
- Tuy nhiên để kiểm soát và tính trước $\max(l, r)$, $\min(l, r)$ rồi xử lý thì rất khó
- Nên để kiểm soát $\max(l, r)$, $\min(l, r)$ dễ hơn thì ta sẽ dùng kĩ thuật chia để trị
- Do ta chỉ cần tính số lượng mảng đẹp $(i, j)$ mà nó đi qua một "chốt" nào đó nên ta sẽ tính trước
- $\max(i, mid)$
- $\max(mid + 1, i)$
- $\min(i, mid)$
- $\min(mid + 1, i)$
- Và khi tính $\max(l, r)$, ta chỉ cần tính $\max(l, mid)$ và $\max(mid + 1, r)$
- Tương tự với $\min(l, r)$
Để biết cách chia để trị "đơn giản hoá" xử lý $\max(l, r)$, $\min(l, r)$ thì các bạn hãy làm thử bài [Tích](https://marisaoj.com/problem/423) trước khi đọc tiếp 😄
#### Thuật toán chi tiết
Gọi $f(l, r)$ là số lượng mảng đẹp
- Ta tính giá trị của $f(l, mid)$ và $f(mid + 1, r)$ với $mid = \frac{l + r}{2}$
- Tính trước các giá trị
- $\max(i, mid)$
- $\max(mid + 1, i)$
- $\min(i, mid)$
- $\min(mid + 1, i)$
- Ta duyệt các $i$ từ $mid + 1$ đến $r$
- Với mỗi $i$, ta tìm $j$ ở nửa phần còn lại sao cho $\max(j, i)$ nằm ở nửa trái
- Và lúc này các vị trí $k$ từ $j$ đến $mid$ là những vị trí ta lưu tâm và có hai loại
1. $\min(k, mid) >= \min(mid + 1, i)$
2. $\min(k, mid) < \min(mid + 1, i)$
- Với loại $1$ thì ta kiểm tra xem có vị trí $j$ nào thoả mãn điều kiện không
- Với loại $2$ cũng tương tự
- Và ta duyệt các vị trí từ $mid$ đến $l$ với cách **gần tương tự**
### Subtask 4 ($20/100$ số điểm): Không có ràng buộc gì thêm
- Với mỗi $i$ ta lần lượt tìm xem phạm vi trái nhất và phải nhất nó có thể vươn tới mà không có hai phần tử bị lặp lại
- Và ta phải di chuyển $j$ khi duyệt $i$ **một cách khéo léo**, đảm bảo $j$ không vượt quá phạm vị trái và phải tương ứng
minhpnk2
Created at
0 likes