Phân tích

Xét \(n\) điểm \(P_i\ (x,y,z,t)\). Ta nói điểm \(A\) thống trị (dominated) điểm \(B\) nếu

• \(A.x<B.x\)
• \(A.y<B.y\)
• \(A.z<B.z\)
• \(A.t<B.t\)

Theo đề bài, mọi giá trị cùng thuộc tính \((x,y,z,t)\) đều phân biệt. Ta cần các định các điểm “không bị thống trị” tức là với mỗi \(B\) không tồn tại \(A\) thỏa mãn 4 điều kiện trên.

Giải pháp Chia để trị

Tiền xử lí: sắp xếp tất cả các điểm theo \(x\) tăng dần.

• Chia: giả sử cần đếm số điểm không bị thống trị trên miền \([l,r]\), chia thành hai miền \([l,m]\) và \([m+1,r]\) với \(m=\left\lfloor \dfrac{l+r}{2}\right\lfloor\)
• Trị: Đệ quy giải cho từng miền \([l,m],[m+1,r]\). Trường hợp cơ sở là độ dài khoảng \(≤1\).
• Kết hợp: Sau khi giải xong hai nửa, ta xử lý các cặp (\(A\) ở nửa trái, \(B\) ở nửa phải) để đánh dấu những B bị thống trị bởi một \(A\) nào đó.

Xử lý bước kết hợp

Để kiểm tra \(A.y<B.y,A.z<B.z\) và \(A.t<B.t\), ta:

• Lấy danh sách các điểm ở hai nửa, chỉ quan tâm tới thuộc tính (y,z,t).
• Sắp xếp chung cả hai nửa theo y tăng.
• Duy trì một Fenwick Tree (BIT) theo \(z\), lưu giá trị nhỏ nhất của \(t\) đã cập nhật, duyệt tất cả điểm (thứ tự \(y\) tăng):
  • Nếu đang xét \(A\) (trong nửa trái): \(update_BIT(z_A,w_A )\).
  • Nếu đang xét \(B\) (trong nửa phải): \(mint = query_BIT(z_B- 1)\); nếu \(mint<B_t\) thì \(B\) bị thống trị.
• Sau khi xử lí xong, roll-back các cập nhật lên BIT.

Vì mỗi bước đệ quy cần \(sort\) mất \(O(n log⁡n)\) và mỗi \(update/query\) BIT tốn \(O(log⁡n)\), tổng độ phức tạp tính toán là \(O(n log^2⁡n)\).