Giả sử một hình chữ nhật có tọa độ $(x_1, y_1, z_1, x_2, y_2, z_2)$ là loại X nếu nó "mỏng" theo chiều $x$, tức là nếu $x_1 = x_2$. Các hình chữ nhật thuộc loại Y và Z cũng được định nghĩa tương tự.
Hãy định nghĩa một hàm $\text{count}(X, Y)$ có chức năng sau:
Chọn tất cả các hình chữ nhật thuộc loại X và Y, sau đó đếm có bao nhiêu cặp hình chữ nhật thỏa mãn điều kiện có ít nhất một hình thuộc loại X và chúng có chung một điểm.
Kết quả tổng thể là $\text{count}(X, Y) + \text{count}(Y, Z) + \text{count}(Z, X)$.

• Thuật toán cho $\text{count}(X, Y)$:
  Giả sử tọa độ $y$ biểu diễn thời gian. Để thời gian trôi và quan sát mặt phẳng $(x, z)$ biểu diễn không gian tại một thời điểm bất kỳ. Các hình chữ nhật loại X trở thành các đoạn thẳng dọc, trong khi các hình chữ nhật loại Y vẫn là các hình chữ nhật.

Các hình chữ nhật loại X có khoảng thời gian tồn tại dương (do $y_1 < y_2$), trong khi các hình chữ nhật loại Y chỉ tồn tại tại một thời điểm duy nhất (do $y_1 = y_2$).

Khi thời gian trôi qua, có ba loại sự kiện có thể xảy ra:

• Một hình chữ nhật loại X bắt đầu.
• Một hình chữ nhật loại Y bắt đầu và kết thúc ngay lập tức.
• Một hình chữ nhật loại X kết thúc.
  Ta sắp xếp các sự kiện theo thời gian và xử lý chúng từng cái một.
  Để đếm tất cả các cặp hình chữ nhật có chung một điểm
  Ta cần, mỗi khi một hình chữ nhật $(x_1, y, z_1, x_2, y, z_2)$ loại Y xuất hiện, trả lời câu hỏi "có bao nhiêu đoạn thẳng dọc trong tập hợp giao với hình chữ nhật $(x_1, z_1, x_2, z_2)$?".

Để đếm tất cả các cặp hình chữ nhật có chung một điểm, sao cho một trong số đó là loại X và một là loại X, ta cần, mỗi khi một hình chữ nhật $(x_1, y, z_1, x_2, y, z_2)$ loại X xuất hiện, trả lời câu hỏi "có bao nhiêu đoạn thẳng dọc trong tập hợp giao với hình chữ nhật (thoái hóa) $(x, z_1, x, z_2)$?".
Cả hai câu hỏi này có thể được trả lời nhanh chóng nếu ta lưu các điểm bắt đầu và kết thúc của tất cả các đoạn thẳng dọc trong cây Fenwick hai chiều (theo kiểu IOI 2001 Mobiles).
Độ phức tạp thời gian:
$\mathcal{O}(N \log N + N \log^2 M)$ với $M$ là tọa độ lớn nhất được cho phép (999 trong bài toán này).