解题思路

把每个乘客记录视为点 (time=J, train=I)，每个查询是固定长度为 X 的时间窗 [S, S+X)，要求统计窗口内出现过的火车编号种类数。

离线处理：

1. 将所有乘客记录按时间 J 升序排序。
2. 将所有查询起点 S（带原下标）按 S 升序排序。
3. 用双指针维护窗口 [S, S+X)：

题目内容

火车站有 $n$ 辆火车，按 $[0,n]$ 编号。现在有 $m$ 名乘客提供了他们要乘坐的火车编号和计划上车的时间点。火车站的工作人员想基于这些信息统计在指定时间的时间区间内。有乘客上车的火车数量。为了简化，时间区间的长度总是为 $X$，火车站的工作人员会提供 $K$ 个起始时间从而构成 $K$ 个时间从而构成 $K$ 个时间区间，现在请你统计在每个时间区间内有乘客上车的火车数量。

注意：时间区间会有重叠

输入描述

• 第 $1$ 行：$N$ $X$ $K$，其中

  • $N$ 是火车数量、取值范围 $[1,100000)$
  • $X$ 是时间区间的跨度，取值范围是 $[1,100000]$
  • $K$ 是要统计的时间区间的个数，取值范围是 $[1,100000]$

• 第 $2$ 行：$S_1S_2...S_K$，总共 $K$ 个数字，每个数字代表一个起始时间，取值范围是 $[0,100000]$

• 第 $3$ 行：$M,M$ 代表乘客数量，取值范围 $[1,100000)$

• 第 $4$ 行：$i,j$，其中

  • $i$ 代表乘客要乘坐的火车编号，取值范围是 $[0,n)$
  • $j$ 代表乘客计划上车的时间，取值范围是 $[0,100000)$

• _：格式同第 $4$ 行

• 第 $M+3$ 行：格式同第 $4$ 行

输出描述

按给定的 $K$ 个起始时间的输入顺序 依次输出每个时间区间内有乘客上车的火车数量，如给定的起始时间是 $3$ $1$ ，则先输出 $3$ 为起始时间的结果，再输出 $1$ 为起始时间的结果

样例1

输入

4 2 2
3 4
4
2 4
2 3
1 2
3 5

输出

1 2

说明

$4$ $2$ $2$ ：总共有 $4$ 辆火车,编号是 $0,1,2,3$，指定时间区间的跨度为 $2$ ，并有 $2$ 个起始时间

$3$ $4$：起始时间分别是 $3$ $4$，时间区间分别是 $[3,3+2),[4,4+2)$

$4$：总共 $4$ 名票客

$2$ $4$：乘客要搭乘火车 $2$，计划在 $4$ 上车，在时间区间 $[3,3+2)$ 和 $[4,4+2)$ 内

$2$ $3$：乘客要搭乘火车 $2$，计划在 $3$ 上车，在时间区间 $[3,3+2)$ 内

$1$ $2$：乘客要搭乘火车 $1$，计划在 $2$ 上车，不在指定的时间区内

$3$ $5$：乘客要搭乘火车 $3$，计划在 $5$ 上车，在时间区间 $[4,4+2)$ 内

可知

• 对于 $[3,3+2)$，火车 $2$ 有两名乘客上车

• 对于 $[4,4+2)$，火车 $2$ 和火车 $3$ 都有乘客上车

因此最后输出 $1$ $2$

样例2

输入

4 5 3
20 10 30
3
3 32
0 14
1 30

输出

0 1 2