Elearning CodePath – CTP Online Judge

Cập Nhật Đoạn và Tìm Kiếm Phần Tử Đầu Tiên Lớn Hơn/Bằng

SEG008

🟢 Hard #Segment Tree #Combinatorics #Interval #Data Structure

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho mảng $A$ có độ dài $N$ chỉ gồm các số nguyên dương. Ta có 2 loại thao tác như sau:

1.  **Cập nhật (Type 1):** `1 l r val` - **Tăng** toàn bộ các phần tử trong đoạn $[l, r]$ lên một lượng $val$.
    $    A[i] \leftarrow A[i] + val, \quad \forall i \in [l, r]$
2.  **Truy vấn (Type 2):** `2 x` - Ta cần tìm vị trí $i$ đầu tiên ($1 \le i \le N$) có $A[i] \ge x$. Nếu tất cả các phần tử đều bé hơn $x$ thì in ra $-1$.

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

* Dòng đầu tiên là số nguyên $N$ (độ dài mảng) và $Q$ (số thao tác).
* Dòng tiếp theo gồm $N$ số nguyên $A[i]$ ($A[i] \le 10^9$).
* $Q$ dòng tiếp theo, mỗi dòng có dạng 1 trong 2 loại thao tác.

Giới hạn:
* $N, Q \le 10^5$.
* $1 \le l \le r \le N$.
* $val \le 1000$.

---
### 📤 Định dạng Đầu ra

Với mỗi thao tác loại 2, in ra đáp án cần tìm (vị trí $i$ đầu tiên thỏa $A[i] \ge x$ hoặc $-1$).

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `6 5` `2 2 0 7 9 7` `2 7` `1 2 3 3` `2 5` `2 2` `2 10` | `4` `2` `1` `-1` |

Giải thích ví dụ: $N=6$. $A = [2, 2, 0, 7, 9, 7]$.
1.  **Thao tác `2 7`:** Tìm $i$ đầu tiên $A[i] \ge 7$.
    * $A[4]=7$. Vị trí đầu tiên là **4**. Output: **4**.
2.  **Thao tác `1 2 3 3`:** $A[2..3] \leftarrow A[i] + 3$.
    * $A$ mới: $[2, 2+3, 0+3, 7, 9, 7] = [2, 5, 3, 7, 9, 7]$.
3.  **Thao tác `2 5`:** Tìm $i$ đầu tiên $A[i] \ge 5$.
    * $A[2]=5$. Vị trí đầu tiên là **2**. Output: **2**.
4.  **Thao tác `2 2`:** Tìm $i$ đầu tiên $A[i] \ge 2$.
    * $A[1]=2$. Vị trí đầu tiên là **1**. Output: **1**.
5.  **Thao tác `2 10`:** Tìm $i$ đầu tiên $A[i] \ge 10$.
    * $\max(A) = 9$. Không có phần tử nào $\ge 10$. Output: **-1**.

---
### 🏷 Ràng buộc

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- | 
| $1$ | $N, Q \le 1000$ | $30\%$ |
| $2$ | $N, Q \le 10^5$ |  $70\%$ |

---

✅ Đã AC: 2 / 5 submissions