AT_abc482_c.Band Count
普及-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.
There are N pieces placed on the grid, and the i-th piece is at (Ri,Ci).
Answer Q queries. Each query is of one of the following 2 types.
1 u d: Print the number of pieces placed in rows u through d.2 l r: Print the number of pieces placed in columns l through r.
有一个 H 行 W 列的网格。用 (i,j) 表示从上往下数第 i 行、从左往右数第 j 列的格子。
网格上放置了 N 个棋子,其中第 i 个棋子位于 (Ri,Ci)。
回答 Q 个查询,每个查询为以下两种类型之一:
1 u d:输出位于第 u 行至第 d 行(含)的所有棋子数量。2 l r:输出位于第 l 列至第 r 列(含)的所有棋子数量。
输入格式
The input is given from Standard Input in the following format:
H W N Q
R1 C1
R2 C2
⋮
RN CN
query1
query2
⋮
queryQ
Each query queryq is given in one of the following formats:
1 u d
2 l r
输入从标准输入中按以下格式给出:
H W N Q
R1 C1
R2 C2
⋮
RN CN
query1
query2
⋮
queryQ
每个查询 queryq 以如下两种格式之一给出:
1 u d
2 l r
输出格式
Print Q lines. The i-th line should contain the answer to the i-th query.
输出 Q 行。第 i 行应包含第 i 个查询的答案。
输入输出样例
输入#1
5 7 5 6 1 1 2 3 2 5 4 3 5 7 1 2 4 2 3 5 1 3 3 2 1 7 1 2 2 2 7 7
输出#1
3 3 0 5 2 1
输入#2
17 23 12 12 14 8 2 19 17 3 7 11 2 4 10 19 7 8 1 23 14 11 2 23 17 19 7 2 1 2 7 2 9 20 1 3 6 2 8 8 1 11 17 2 1 23 1 1 1 2 20 22 1 7 14 2 3 11 1 15 17 2 19 23
输出#2
6 5 0 2 4 12 1 0 6 6 2 5
说明/提示
Sample 1 Explanation:
For the 1-st query, the pieces in rows 2 through 4 are the 2-nd, 3-rd, and 4-th pieces, for a total of 3.
Constraints
- 1≤H,W≤109
- 1≤N≤min(H×W,3×105)
- 1≤Ri≤H
- 1≤Ci≤W
- (Ri,Ci)=(Rj,Cj) if i=j.
- 1≤Q≤3×105
- 1≤u≤d≤H
- 1≤l≤r≤W
- All input values are integers.
样例 1 解释:
对于第 1 个查询,位于第 2 行至第 4 行的棋子分别是第 2、第 3 和第 4 个棋子,共计 3 个。
约束条件
- 1≤H,W≤109
- 1≤N≤min(H×W,3×105)
- 1≤Ri≤H
- 1≤Ci≤W
- 当 i=j 时,(Ri,Ci)=(Rj,Cj)。
- 1≤Q≤3×105
- 1≤u≤d≤H
- 1≤l≤r≤W
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?