NOI '20 P3 - Tears

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem type

Let (a,b) \le (c,d) denote two points (a,b),(c,d) on the plane satisfies a \le c,b \le d. There are n events denoted by n distinct points \{(x_i,y_i)\}_{i=1}^n on the plane. There are m epochs denoted by a rectangle (r_{i,1},r_{i,2},c_{i,1},c_{i,2}) where (r_{i,1},c_{i,1}) is the bottom-left corner of the rectangle and (r_{i,2},c_{i,2}) is the upper-right corner, and it is guaranteed that (r_{i,1},c_{i,1}) \le (r_{i,2},c_{i,2}). We say epoch i includes event j if and only if (r_{i,1},c_{i,1}) \le (x_j,y_j) \le (r_{i,2},c_{i,2}).

If two events i,j satisfy (x_i,y_i) \le (x_j,y_j), then the two events constitute an occurrence of sadness. For all events in an epoch, the occurrences of sadness are called the tear of the epoch, and the size of the tear of the epoch is measured by the number of occurrences of sadness. We'd like to compute the size of the tears of the epochs.

Input Specification

The first line contains two integers n,m denoting the number of events and the number of epochs. The second line contains n integers p_i, and the i-th number denotes event i has coordinate (i,p_i) on the plane. It is guaranteed that p_i is a permutation of 1, 2, \dots, n. In the following m lines, each line contains four integers r_{i,1},r_{i,2},c_{i,1},c_{i,2} denoting the rectangle corresponding to the epoch.

Output Specification

There are m lines and each line contains an integer. The i-th line denotes the size of the tear of epoch i.

Sample Input 1

9 9
9 8 7 6 2 4 5 3 1
4 9 3 6
2 9 1 8
3 8 2 4
3 9 2 7
2 8 1 6
1 9 1 9
1 3 5 7
2 3 3 3
6 6 6 6

Sample Output 1

1
4
2
4
4
4
0
0
0

For all test cases, 1 \le n \le 10^5, 1 \le m \le 2 \times 10^5, 1 \le r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2} \le n.

Test CasenmAdditional Constraints
1~31010None.
43\,0003\,000
54\,0004\,000
65\,0005\,000
725\,00025\,000For every epoch i, we have c_{i,1} = 1 and c_{i,2} = n.
850\,000100\,000
975\,000150\,000
10100\,000200\,000
1160\,000120\,000For any two rectangles representing different epochs, either one is contained in another (the boundaries may overlap) or they are disjoint.
1280\,000160\,000
13100\,000200\,000
1420\,00020\,000None.
1530\,00030\,000
1640\,00040\,000
1750\,00050\,000
1860\,00060\,000
1970\,00070\,000
20~22100\,000200\,000There exists at most 50 pairs of events (i,j) (1 \le i < j \le n) that do not satisfy (i,p_i) \le (j,p_j).
23~25100\,000200\,000None.

Comments

There are no comments at the moment.