Những kiến thức cần nắm trước khi xem:

1. Mảng cộng dồn (Prefix sum).

2. Chia căn (SQRT Decomposition).

3. Cây chỉ số nhị phân (Fenwick Tree / BIT).

Gọi hình chữ nhật con có góc trái trên ~(x_1,y_1)~ và góc phải dưới ~(x_2,y_2)~ là hình chữ nhật ~(x_1,y_1,x_2,y_2)~.

Để trả lời các truy vấn, ta chia hình chữ nhật ~(x_1, y_1, x_2, y_2)~ thành ~4~ hình chữ nhật sau :~(1, 1, x_2, y_2)~, ~(1, 1, x_1-1, y_2)~, ~(1, 1, x_2, y_1-1)~ và ~(1, 1, x_1-1, y_1-1)~ giống như cách lấy tổng từ mảng cộng dồn hai chiều.

CTDL: Cấu trúc dữ liệu.

Subtask 1 ~(N \leq 1000)~

Ta có thể chọn CTDL ~S~ chứa những đoạn ~[1,x], \forall x \in [1,N]~ vì tổng độ dài là ~\frac{N(N+1)}{2}~ không vượt quá ~10^6~ với ~N~ tối đa trong subtask này. Mỗi truy vấn cần tối đa bốn câu hỏi.

Subtask 2 (~N \leq 3000~ và các truy vấn thỏa mãn ~(x_1 - 1), (y_1 - 1), x_2, y_2~ đều chia hết cho ~100~)

Với ~x \in \left[1, \frac{N}{100}\right]~ ta thêm đoạn thẳng ~[(x-1) \times 100 + 1, x \times 100]~ vào CTDL ~S~, ta có ~M=\frac{N}{100}~ và tổng độ dài các đoạn trong ~S \approx N~ nên không thể quá ~10^6~.

Hình dung từ CTDL ~S~ và bảng ~N^2~, ta tạo một bảng mới có kích thước ~\left(\frac{N}{100}\right)^2~. Bảng này có tối đa ~\left(\frac{3000} {100}\right)^2=900~ ô. Vậy hiển nhiên ta để trả lời ~1~ truy vấn ta tốn không quá ~900~ câu hỏi.

Subtask 3 (Không có điều kiện gì thêm)

Ta sử dụng CTDL ~S~ như cấu trúc dữ liệu cây chỉ số nhị phân, với mỗi ~x \in [1, N]~ chúng ta thêm vào ~S~ đoạn thẳng ~[x-x\&(-x)+1,x]~ ở đây theo nguyên tắc phép bù ~2~ ~x\&(-x)~ có giá trị bằng ~2^k~ với ~k~ là vị trí bit ~1~ đầu tiên về bên phải trong biểu diễn nhị phân của số ~x~.

Hiển nhiên cây chỉ số nhị phân có ~N~ node nên số phần tử của ~S~ là ~N~, vậy ta chỉ cần chứng minh rằng tổng độ dài các đoạn thẳng trong ~S~ không quá ~10^6~:

• Với ~k~ bất kỳ, ta có đóng góp của ~2^k~ vào tổng độ dài các đoạn thẳng là xấp xỉ ~\frac{N}{2^{k+1}}~.

• Vì ~\log_2 N \approx 16~ với ~N~ tối đa nên ta chỉ xét ~k \in [0,16]~, vậy ta ước lượng tổng độ dài các đoạn thẳng là xấp xỉ: $$\sum_0^{16} 2^k \frac{N}{2^{k+1}} = 17 \times \frac{N}{2} = 850000.$$

Vì tất cả các hình chữ nhật này đều có góc trái trên ở ô ~(1, 1)~ nên ta có thể dùng CTDL ~S~ như cây chỉ số nhị phân hai chiều để tính tổng giá trị của chúng. Vì các số trong khoảng ~[1, 10^5]~ có tối đa ~16~ bit ~1~ trong biểu diễn nhị phân nên với một hình chữ nhật ta mất nhiều nhất ~16^2~ truy vấn để tính tổng, vậy ~4~ hình chữ nhật mất tối đa là ~4 \times 16^2 = 2^{10} = 1024~ truy vấn.