### 1. Xử lý truy vấn 1 và 2.
Xét khi xử lý truy vấn 1.
Trước tiên, ta chia đoạn cần xử lý ra thành phần thừa bên ngoài và phần còn lại như bình thường.
#### 1.1. Xử lý phần thừa:
Giả sử ta có mảng $T_x$ là tổng đóng góp vào $a_x$ sau khi cập nhật các phần thừa bên ngoài.
Vậy, khi cập nhật, ta sẽ cần cộng vào 1 phần tử, và khi truy vấn thì sẽ là truy vấn đoạn.
Do ta cần cập nhật $T_x$ $O(q\sqrt{n})$ lần, nhưng chỉ truy vấn $O(q)$ lần, nên ta sẽ dùng chia căn để xử lý $T_x$ (cập nhật: cộng vào block tương ứng, truy vấn: làm như bình thường).
Điều này giúp cân bằng ĐPT truy vấn và cập nhật, giảm thời gian xuống $O(q\sqrt{n})$.
#### 1.2. Xử lý các block:
Trước tiên, ta lưu mảng $F_i$ là giá trị thêm vào cho block thứ $i$ ($a_{p_{i\cdot B}},...,a_{p_{(i+1)\cdot B-1}}$).
Ta lưu thêm mảng $M_{i,j}$ là số lượng giá trị nằm trong block hoán vị thứ $i$ mà $\leq j$.
Khi xử lý truy vấn 1, ta cập nhật $F_i$ như bình thường.
Khi xử lý truy vấn 2, ta lặp qua các block trong đoạn, và tính tổng $F_i \cdot (M_{i,r}-M_{i,{l-1}})$ với $i$ là chỉ số block ta đang xét đến.
#### Tổng đpt cho phần này là $O((n+q)\sqrt{n})$. Vậy bài toán trên đã được giải quyết với đpt $O((n+q)\sqrt{n})$.
### 2. Biến đổi bài toán gốc về bài toán trên:
Ta nhận thấy rằng truy vấn $1$ và truy vấn $3$, tương tự như truy vấn $0$ và truy vấn $2$, thực chất chỉ là bài toán cộng vào đoạn và tính tổng đoạn. Bài toán này có nhiều cách làm và là bài toán điển hình, nên sẽ không được nói đến ở đây.
#### Về việc xử lý truy vấn $0$ và truy vấn $3$:
Nhận thấy rằng truy vấn 0 thực chất là cộng vào $a_{p_{{p^{-1}}\_i}}$ với $l\leq i \leq r$, và truy vấn 3 bảo bạn tính tổng $a_{p_{i}}$ với $l\leq i \leq r$.
Vậy, ta có thể đặt $b_i = a_{p_i}$, và bài toán chuyển về bài toán con với hoán vị $p^{-1}$.
#### Đpt tổng: $O((n+q)\sqrt{n})$ thời gian, $O(n\sqrt{n})$ bộ nhớ.
pt48583994
Created at
2 likes