Elearning CodePath – CTP Online Judge

Biển có mang

MCB

🟢 Hard #Fenwick Tree #Sliding Window #Stack #Data Structure

### Thông tin chung

| Mục | Nội dung |
| --- | --- |
| **Tên Bài Toán** | **Biển có mang** |
| **Input** | số nguyên dương $n$ và $n$ số nguyên dương $a_i$ |
| **Output** | số nguyên dương duy nhất là số lượng dãy con liên tiếp thỏa mãn điều kiện |
| **File Input** | `DAYKEP.INP` |
| **File Ouput** | `DAYKEP.OUT` |

Được ngày đẹp giời, QUANSENSEI ngồi viết đề bài cầm đi đố mấy bọn trẻ mẫu giáo. Đề bài thầy ra như sau: "Cho dãy A với n phần tử, đếm số lượng dãy con (không cần liên tiếp) thỏa mãn điều kiện: Nếu $i_1 \le i_2 \le...\le i_k$ thì $a_{i_1} \le a_{i_2} \le ... \le a_{i_k}$. "

Đằng sau chỗ thầy ngồi, T bỗng đọc được đề thầy viết, nhưng vì đọc thiếu dẫu ba chấm và chữ không cần liên tiếp, nên sau khi ngồi suy nghĩ một hồi, T nghĩ đề QUANSENSEI sang thế này:

"Cho dãy A với n phần tử, đếm số lượng dãy con liên tiếp $B$ thỏa mãn điều kiện: $\forall a_i \in B,$ gọi $val1$ và $val2$ lần lượt là phần tử đầu tiên và cuối cùng của dãy $B$, $val1 \le a_i \le val2$.""

Nghĩ mãi không ra cách giải, T quyết định nhờ bạn giải hộ và giảng lại.

### Định dạng đầu vào

- Dòng đầu là số nguyên dương $n$ $(1 \le n \le 10^6$)
  
- Tiếp theo là $n$ số nguyên $a_i$ trên một dòng $(1 \le a_i \le 10^9)$.

### Định dạng đầu ra

- In ra số nguyên duy nhất là số lượng dãy con liên tiếp thỏa mãn điều kiện.

### Ví dụ (Sample Test)

| Input (`DAYKEP.INP`) | Output (`DAYKEP.OUT`) |
| --- | --- |
| `5` <br/>`1 2 3 4 5` | `11` |
| `8`<br/>`2 1 6 3 6 7 8 5` | `18` |

### <u>Subtask</u>:

- Có $20$% số điểm có $n \le 300$
  
- Có $40$% số điểm có $n <= 5000$
  
- $40$% số điểm còn lại không có ràng buộc gì thêm

✅ Đã AC: 2 / 6 submissions