#5228. Đếm đoạn lồng nhau (Mã bài: NESTSEG)

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho n đoạn thẳng trên trục số, đoạn thứ i có dạng [l_i, r_i] . Ta nói đoạn i được chứa trong đoạn j nếu l_j \le l_i r_i \le r_j . Với mỗi đoạn i , hãy đếm xem có bao nhiêu đoạn j chứa đoạn i .

Dữ liệu:

  • Dòng đầu tiên chứa số nguyên n ( 1 \le n \le 200000 ).
  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên l_i, r_i ( -10^9 \le l_i \le r_i \le 10^9 ) là hai đầu mút của đoạn thứ i .

Kết quả: In ra n số nguyên trên một dòng, số thứ i là câu trả lời cho đoạn thứ i theo thứ tự xuất hiện trong input.

Ví dụ:

Dữ liệu:

4
1 8
2 3
4 7
5 6

Kết quả:

0 1 1 2