486 . [Tutorial] 點與線段
.jpg)
Description
給定 $N$ 個一維數線，其中第 $i$ 個數線包含區間 $[l_i, r_i]$ 的點。請回答 $Q$ 筆詢問，其中第 $i$ 個詢問會給定一整數點 $x_i$，請計算有幾個線段包含該整數點。
更具體來說，對每個詢問請回答有幾個 $j$ 滿足 $1 \leq j \leq N$ 且 $l_j \leq x_i \leq r_j$。
Input Format
輸入第一行有兩個正整數 $N, Q$。
接下來 $N$ 行，第 $i$ 行有兩個正整數 $l_i, r_i$。
接下來一行包含 $Q$ 個正整數 $x_1, x_2, \ldots, x_Q$。
- $1 \leq N, Q \leq 5 \times 10^ 5$
- $1 \leq l_i \leq r_i \leq 10^ 9$
- $1 \leq x_i \leq 10^ 9$
Output Format
請輸出一行，該行有 $Q$ 個整數，其中第 $i$ 個為第 $i$ 筆詢問的答案。
Sample Input 1
10 9 5 6 5 7 2 3 1 7 3 8 4 7 1 8 3 9 7 9 56562 56562 8 6 4 1 9 7 5 3 2
Sample Output 1
4 7 5 2 2 7 7 5 3
Hints
Problem Source
程式解題社教學題。
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~20 | 無額外限制 | 100 |