# 原始题目

## D - AtCoder Express 2

• Time limit : 3sec / Memory limit : 1000MB
• Score: 400 points

### Problem Statement

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, …, N from west to east. A company called AtCoder Express possesses M trains, and the train i runs from City Li to City Ri (it is possible that Li=Ri). Takahashi the king is interested in the following Q matters:

The number of the trains that runs strictly within the section from City pi to City qi, that is, the number of trains j such that pi≤Lj and Rj≤qi.

Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

### Constraints

• N is an integer between 1 and 500 (inclusive).
• M is an integer between 1 and 200 000 (inclusive).
• Q is an integer between 1 and 100 000 (inclusive).
• 1≤Li≤Ri≤N (1≤i≤M)
• 1≤pi≤qi≤N (1≤i≤Q)

### Input

Input is given from Standard Input in the following format:

N M Q
L1 R1
L2 R2
:
LM RM
p1 q1
p2 q2
:
pQ qQ

### Output

Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City pi to City qi.

2 3 1
1 1
1 2
2 2
1 2

### Sample Output 1

3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

10 3 2
1 5
2 8
7 10
1 7
3 10

### Sample Output 2

1
1

The first query is on the section from City 1 to 7. There is only one train that runs strictly within that section: Train 1. The second query is on the section from City 3 to 10. There is only one train that runs strictly within that section: Train 3.

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

7
9
10
6
8
9
6
7
8
10

# 解题思路

• 暴力：由于只需要计数，那么以每个城市为集合，统计该城市出发的列车的行使距离，对于每次询问，遍历pi到qi城市的集合判断距离是否小于终点到遍历点的距离即可。

• DP：

• 把列车行驶看作线段，很明显大的线段包含小的线段。由此联想可以由内向外扩展，考虑DP
• 以终点作为集合，元素为起始点，预处理后对每个集合排序（代码实际应用vector而非set，因为set不支持迭代器随机访问而且可能会有重复线路）
• $dp[i][j]$表示从i城市到j城市包含的火车线路。
• 则状态转移方程为$dp[i][j]=dp[i][j-1]+num[i][j]$ ，$num[i][j]$表示到达j城市且起点不在i城市之前的列车线路数。
• 求$num[i][j]$，用二分查找lower_bound找到j城市集合中第一个大于等于i的位置，$num[i][j]$即为size减去前缀。
• 预处理后直接可以输出答案

• 暴力
• DP

# 收获与反思

• 脑子里别老想着暴力，有重复计算又没有修改为什么不考虑记忆化搜索？不考虑DP？思维训练还不够
• 很明显的时间差异。