Đoạn thẳng lồng nhau

Buổi 26 — Fenwick Tree Data-structures sorting
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho $N$ đoạn thẳng trên trục số, đoạn thứ $i$ là $[L_i, R_i]$ (các đoạn đôi một khác nhau, tức là không có hai đoạn nào có cùng cả $L$ và $R$). Với mỗi đoạn $i$, hãy đếm xem có bao nhiêu đoạn $j \ne i$ nằm bên trong đoạn $i$ (tức là $L_i \le L_j$ và $R_j \le R_i$).

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $L_i, R_i$ ($1 \le L_i \le R_i \le 10^9$).
Dữ liệu ra
  • In ra $N$ số nguyên trên một dòng, số thứ $i$ là số lượng đoạn thẳng nằm bên trong đoạn $i$.
Ví dụ
Input Output
4
1 6
2 4
4 8
3 6
2 0 0 0
Giới hạn
  • $1 \le N \le 10^5, 1 \le L_i \le R_i \le 10^9$
Draft saved