AT_abc482_c.Band Count

普及-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There is a grid with HH rows and WW columns. Let (i,j)(i,j) denote the cell at the ii-th row from the top and the jj-th column from the left.
There are NN pieces placed on the grid, and the ii-th piece is at (Ri,Ci)(R_i, C_i).
Answer QQ queries. Each query is of one of the following 22 types.

  • 1 u d: Print the number of pieces placed in rows uu through dd.
  • 2 l r: Print the number of pieces placed in columns ll through rr.

有一个 HH 行 WW 列的网格。用 (i,j)(i,j) 表示从上往下数第 ii 行、从左往右数第 jj 列的格子。
网格上放置了 NN 个棋子,其中第 ii 个棋子位于 (Ri,Ci)(R_i, C_i)。
回答 QQ 个查询,每个查询为以下两种类型之一:

  • 1 u d:输出位于第 uu 行至第 dd 行(含)的所有棋子数量。
  • 2 l r:输出位于第 ll 列至第 rr 列(含)的所有棋子数量。

输入格式

The input is given from Standard Input in the following format:

HH WW NN QQ
R1R_1 C1C_1
R2R_2 C2C_2
⋮\vdots
RNR_N CNC_N
query1\mathrm{query}_1
query2\mathrm{query}_2
⋮\vdots
queryQ\mathrm{query}_Q

Each query queryq\mathrm{query}_q is given in one of the following formats:

11 uu dd

22 ll rr

输入从标准输入中按以下格式给出:

HH WW NN QQ
R1R_1 C1C_1
R2R_2 C2C_2
⋮\vdots
RNR_N CNC_N
query1\mathrm{query}_1
query2\mathrm{query}_2
⋮\vdots
queryQ\mathrm{query}_Q

每个查询 queryq\mathrm{query}_q 以如下两种格式之一给出:

11 uu dd

22 ll rr

输出格式

Print QQ lines. The ii-th line should contain the answer to the ii-th query.

输出 QQ 行。第 ii 行应包含第 ii 个查询的答案。

输入输出样例

  • 输入#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 11-st query, the pieces in rows 22 through 44 are the 22-nd, 33-rd, and 44-th pieces, for a total of 33.

Constraints

  • 1≤H,W≤1091 \leq H, W \leq 10^9
  • 1≤N≤min⁡(H×W,3×105)1 \leq N \leq \min(H \times W, 3 \times 10^5)
  • 1≤Ri≤H1 \leq R_i \leq H
  • 1≤Ci≤W1 \leq C_i \leq W
  • (Ri,Ci)≠(Rj,Cj)(R_i, C_i) \neq (R_j, C_j) if i≠ji \neq j.
  • 1≤Q≤3×1051 \leq Q \leq 3 \times 10^5
  • 1≤u≤d≤H1 \leq u \leq d \leq H
  • 1≤l≤r≤W1 \leq l \leq r \leq W
  • All input values are integers.

样例 1 解释:
对于第 11 个查询,位于第 22 行至第 44 行的棋子分别是第 22、第 33 和第 44 个棋子,共计 33 个。

约束条件

  • 1≤H,W≤1091 \leq H, W \leq 10^9
  • 1≤N≤min⁡(H×W,3×105)1 \leq N \leq \min(H \times W, 3 \times 10^5)
  • 1≤Ri≤H1 \leq R_i \leq H
  • 1≤Ci≤W1 \leq C_i \leq W
  • 当 i≠ji \neq j 时,(Ri,Ci)≠(Rj,Cj)(R_i, C_i) \neq (R_j, C_j)。
  • 1≤Q≤3×1051 \leq Q \leq 3 \times 10^5
  • 1≤u≤d≤H1 \leq u \leq d \leq H
  • 1≤l≤r≤W1 \leq l \leq r \leq W
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页