## Lời giải bài SDIFF
### Tác giả: Lý Huỳnh Minh Đăng, I2124

## 1. Tóm tắt đề
- Cho dãy số nguyên $a$ gồm $n$ phần tử $(1 \le n \le 5 \times 10^6)$ được tạo bởi 3 số nguyên không âm $p, q, m$ với công thức :

\begin{gather*} a_i = (p \times i+q) \ mod \ m \end{gather*}

- Yêu cầu: Với số nguyên $k$, đếm số lượng dãy con liên tiếp trong $a$ có độ lệch không quá $k$.

> *Độ lệch là hiệu số của phần tử lớn nhất và nhỏ nhất của dãy con liên tiếp.*

## 1.1. Khởi tạo mảng
- Áp dụng công thức đề cho, tạo mảng $a$ trong thời gian tuyến tính.
>*Ví dụ với 𝑛 = 5, 𝑝 = 3, 𝑞 = 0, 𝑚 = 5, dãy a sẽ là (3,1,4,2,0)*
- Độ phức tạp: $O(n)$

## 2. Thuật toán ngây thơ

- Với mỗi chỉ số $i = 1,2,..,n \ (1 \le i\le n)$, ta duyệt qua các giá trị $a_j \ (j=i,i-1,...,1)$, kết quả bài toán là :
\begin{gather*}
\sum_{i=1}^{n} \ i-j_{end}+1
\end{gather*} với $j_{end}$ là vị trí cuối cùng mà $max(a[j_{end}..i])-min(a[j_{end}..i]) \le k$
- **Độ phức tạp**: $O(n^2)$

## 3. Cải tiến
- Ta sử dụng hai con trỏ $l,r$ bắt đầu với giá trị $l=1,r=1$.
- Với mỗi giá trị $l$ ta sẽ tăng dần $r$ cho tới khi không còn giữ được tính chất $max(a[l..r])-min(a[l..r]) \le k$. Khi đó ta cộng $r-l$ vào kết quả và tiếp tục tăng $l$.
- Để thực hiện việc lấy nhanh giá trị $max(a[l..r])$ và $min(a[l..r])$ thì ta sử dụng cấu trúc dữ liệu [Segment Tree](https://cp-algorithms.com/data_structures/segment_tree.html) tính toán trong $O(log(n))$ hoặc [Sparse Table](https://cp-algorithms.com/data_structures/sparse-table.html) trong $O(1)$, cả hai CTDL này được xây dựng trong $O(n \times log(n))$.
- **Độ phức tạp**: $O(n \times log(n))$
#### Code mẫu: [Link](https://ideone.com/kVtuB6)

## 4. Tối ưu
- Tuy thuật toán cải tiến đã giảm độ phức tạp xuống còn $O(n \times log(n))$ nhưng với giới hạn đề cho $(n<=5 \times 10^6)$ thì máy chấm thông thường sẽ không chạy được trong vòng 1 giây.
- Vì vậy ta cần một kiểu dữ liệu container chứa 1 dãy số liên tiếp mà ta có thể thao tác với hai giá trị đầu, cuối của container (nhập, xóa,...). CTDL thích hợp đã có trong STL Library của C++ là [Deque](https://vnoi.info/wiki/algo/data-structures/Deque).
- Ta sử dụng 2 container là $dequeMin$ và $dequeMax$. Gọi :
+ $dqMin_{front}, \ dqMin_{back}$ là chỉ số trong $a$ của phần tử đầu và cuối của $dequeMin$.
+ $dqMax_{front}, \ dqMax_{back}$ là chỉ số trong $a$ của phần tử đầu và cuối của $dequeMax$.
+ Biến $pre$ duy trì chỉ số đầu tiên trong $a$ mà còn thỏa $max(a[pre..i])-min(a[pre..i]) \le k$

- Với mỗi giá trị $a_i$ ,ta sẽ thực hiện 4 thao tác :
1. Nếu $a[dqMin_{back}]>a_i$ thì ta thực hiện xóa phần tử $dqMin_{back}$ cho tới khi $a[dqMin_{back}] \le a_i$. Sau đó đẩy $a[i]$ vào $dqMin_{back}$.
2. Nếu $a[dqMax_{back}]<a_i$ thì ta thực hiện xóa phần tử $dqMax_{back}$ cho tới khi $a[dqMax_{back}] \ge a_i$. Sau đó đẩy $a[i]$ vào $dqMax_{back}$.

>Việc xóa và cập nhật $a_i$ liên tục vào $dequeMin, \ dequeMax$ sẽ đảm bảo giá trị $Min,Max$ của đoạn $a[pre..l]$.
3. *Sau hai bước trên thì một trong hai $deque$ sẽ chỉ còn một phần tử. Nghĩa là một trong hai phần tử $dqMin_{front}, \ dqMax_{front}$ chắc chắn chứa $min(a[pre..i])$ hoặc $max(a[pre..i])$.
+ Kiểm tra nếu $a[dqMax_{front}]-a[dqMin_{front}] > k$ thì ta sẽ tăng $pre$ lên.
+ Cùng lúc xóa các phần tử $dqMin_{front}, dqMax_{front}$ nếu chúng nhỏ hơn $pre$ cho tới khi thỏa $a[dqMax_{front}]-a[dqMin_{front}] \le k$.
4. Cộng giá trị $i-pre+1$ (tương ứng với số đoạn con thỏa điều kiện trong $a[pre..i]$) vào kết quả.
- **Độ phức tạp**: $O(n)$

### Code mẫu: [Link](https://ideone.com/QLSNz9)
### Tag: Data Structure, Two-pointer