Ta sẽ giải quyết bài toán trên bằng cách chia mảng $a$ ra thành $n/S$ block với $S$ là số phần tử của mỗi block
Ta nhận thấy rằng sau mỗi truy vấn 1, tổng của mảng $a$ sẽ luôn giảm nếu tồn tại phần tử thỏa $a_i > x$
. Từ đó, với mỗi block ta chỉ cần những phần tử lớn hơn $x$ và ta chỉ quan tâm tối đa $MaxA$ phần tử trên mỗi block sau $q$ truy vấn
Vấn đề bây giờ là cách để cập nhật block sao cho mỗi block chỉ duyệt tối đa $MaxA$
* Mỗi block ta lưu 2 biến $mx$ là phần tử lớn nhất có thể trong block và $lazy$ là biến lười cho biết rằng giá trị thực của cả block là $a_i - lazy$
* Ở đây ta sẽ dùng DSU để đại diện cho các giá trị
- Ví dụ: mảng block đang có $[X, X, Y, Y, Z, Z, Z]$ thì khi ta cho phép gán tất cả giá trị $X$ thành giá trị $Z$ thì ta không cần duyệt qua từng phần tử mà chỉ cần cho $Z$ là cha của $X$ là xong.
Truy vấn 1 ta sẽ duyệt qua từng block, với mỗi block ta sẽ có 2 trường hợp:
* $2x \le mx - lazy$
- Ta sẽ gán các giá trị $i \le x$ thành $i + x$, sau đó cộng $lazy$ lên $x$. Việc này đúng bởi vì các giá trị lớn hơn $x$ đều được trừ đi $x$ qua $lazy$ và những giá trị bé hơn hoặc bằng $x$ đều được cộng lên $x$ sau đó cùng bị trừ đi $x$ qua $lazy$.
* $2x > mx - lazy$
- Ta sẽ trực tiếp gán các giá trị $i$ lớn hơn $x$ thành $i-x$.
- Khi đó biến $mx$ đã bị giảm nên ta cũng cần phải cập nhật lại.
* Còn trường hợp biên của $l$ và $r$ thì ta chỉ cần chuẩn hóa lại block là xong.
Tại sao lại chia ra 2 trường hợp?
Bằng cách chia 2 trường hợp trên, mỗi truy vấn thì một block chỉ xử lý $\min(x, mx - lazy - x)$ (biết rằng $mx - lazy$ là giá trị thực lớn nhất trong block). Khi này số lần lặp cho mỗi block chắc chắn bé hơn hoặc bằng $MaxA$. Phần chứng minh xin mời bạn đọc thử sức.
Độ phức tạp của $q$ truy vấn là $O(q\times\frac{n}{S})$ và mỗi block chỉ duyệt tối đa $MaxA$ nên độ phức tạp là $O(MaxA\times\frac{n}{S})$. Ta có độ phức tạp tổng là $O((q + MaxA) \times\frac{n}{S})$, chỉ cần cho $S$ là $\sqrt{n}$ là có thể qua.
Shiba_Engine
Created at
1 likes