Within 2 - MarisaOJ: Marisa Online Judge

Given

$n$ line segments lying on the number line, the

$i$ -th segment starts from

$l_i$ and ends at

$r_i$ . Segment

$j$ is said to be within segment

$i$ if

$l_i \leq l_j \leq r_j \leq r_i$ . For each segment, count the number of line segments within it (excluding itself). ### Input - The first line contains an integer

$n$ . - The next

$n$ lines, each line contains two integers

$l_i$ and

$r_i$ . ### Output - Print

$n$ integers, where the

$i$ -th integer represents the number of line segments within the

$i$ -th segment. ### Constraints -

$1 \le n \le 10^5$ . -

$1 \le l_i \le r_i \le 10^5$ . ### Example Input

$4 2 3 4 6 8 8 2 4$

Output

$0 0 0 1$

Introduction to Segment Tree and Binary Indexed Tree
	Point update, sum query
	Point update, minimum query
	Range update, sum query
	Range update, minimum query
	Apple picking
	Non-negative subarray
	Inversions
	K-query
	Divisible by 3
	Mushroom harvesting
	KSS
	D-query
	Greatest subarray sum
	Copying data
	Within 1
	Within 2
	Ladder update
	Racing
	One time
	Subarray XOR
	String sorting
	Odd query
	Full sequence

Topic

Data structure

Rating

1600

Solution (0)

Solution