Elearning CodePath – CTP Online Judge

BIT Truy vấn Max Xuôi/Ngược

MAXBIT

🟢 Easy #Segment Tree

### 📌 Thông tin chung

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

Cho mảng $A$ gồm $N$ số nguyên, $A = (A_1, A_2, \dots, A_N)$.
Yêu cầu thực hiện $Q$ truy vấn trên mảng này. Mỗi truy vấn thuộc một trong bốn loại sau:

* **Loại 1** (`1 u w`): Tăng giá trị của phần tử $A_u$ lên một lượng $w$.
    $$
    A_u \leftarrow A_u + w
    $$
* **Loại 2** (`2 u v`): Gán giá trị $v$ cho phần tử $A_u$.
    $$
    A_u \leftarrow v
    $$
* **Loại 3** (`3 u`): Tính giá trị lớn nhất của các phần tử từ đầu mảng đến vị trí $u$.
    $$
    \text{Kết quả} = \max_{1 \le i \le u} A_i
    $$
* **Loại 4** (`4 u`): Tính giá trị lớn nhất của các phần tử từ vị trí $u$ đến cuối mảng.
    $$
    \text{Kết quả} = \max_{u \le i \le N} A_i
    $$

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

Dữ liệu vào từ file `MAXBIT.INP`:

* Dòng 1: Ghi số nguyên dương $N$.
* Dòng 2: Ghi $N$ số nguyên $A_1, A_2, \dots, A_N$ - mảng ban đầu.
* Dòng 3: Ghi số nguyên dương $Q$.
* $Q$ dòng cuối cùng: Mỗi dòng ghi một truy vấn theo quy cách mô tả ở trên.

Giới hạn:
* $1 \le N \le 10^5$.
* $1 \le Q \le 10^5$.
* $-10^9 \le A_i, w, v \le 10^9$.

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

Ghi ra file `MAXBIT.OUT`. Với các truy vấn loại 3 và loại 4, in ra kết quả tìm được trên một dòng riêng biệt.

---
### ✨ Ví dụ

| Input (`MAXBIT.INP`) | Output (`MAXBIT.OUT`) |
| :--- | :--- |
| `5` `1 2 3 4 5` `5` `1 5 3` `2 3 7` `3 2` `4 3` `4 1` | `2` `8` `8` |

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N, Q \le 5000$ | $40\%$ |
| 2 | $N, Q \le 10^5$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions