Thành phố Cuồng loạn

Trong các cấu trúc dữ liệu phân đoạn như Segment Tree (Cây phân đoạn) hay các loại cây cân bằng, hàm pushdown đóng vai trò then chốt trong việc tối ưu hóa hiệu suất. Kỹ thuật này thường được gọi là Lazy Propagation (Lan truyền lười), cho phép chúng ta trì hoãn việc cập nhật các nút con cho đến khi thực sự cần thiết, từ đó giảm độ phức tạp từ $O ...

Lý Siêu Thụ (Li Chao Tree) là một cấu trúc dữ liệu dựa trên cây phân đoạn, dùng để giải quyết các bài toán liên quan đến việc duy trì một tập hợp các hàm bậc nhất (đường thẳng hoặc đoạn thẳng) và hỗ trợ truy vấn giá trị lớn nhất (hoặc nhỏ nhất) tại một hoành độ cụ thể. Nguyên lý cơ bản Mỗi nút trong cây phân đoạn lưu trữ một "đường thẳng ưu th ...

Bài 1: Tổng số cặp số tốt I Đối với bài toán này, chúng ta cần đếm số lượng cặp chỉ số (i, j) sao cho nums1[i] chia hết cho nums2[j] * k. Do giới hạn kích thước của mảng là nhỏ (n, m <= 50), chúng ta có thể sử dụng phương pháp mô phỏng trực tiếp (brute-force) bằng cách duyệt qua tất cả các cặp có thể. class Solution { public: int numberO ...

Bài toán yêu cầu xử lý các truy vấn, mỗi truy vấn cho hai số l và r, cần tính tổng giá trị nhỏ nhất trên tất cả các đoạn con của đoạn [l, r]. Với các truy vấn có thể xử lý offline, ta có thể áp dụng thuật toán Mo. Vấn đề chính là tính đóng góp khi mở rộng đầu phải thêm một phần tử. Các đoạn con mới sinh ra đều có đầu phải là r. Ta cần tính tổn ...