← 返回题目列表

AtCoder · awc0107_e

E. 休息时间优化

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥在半开时段代表的营业时间内负责服务柜台 [0, T)。时间作为整数处理。

在工作时间内,高桥必须恰好连续休息一次长度 D。如果休息时间开始 S,则中断周期(计数器关闭时)为半开区间 [S, S+D). S 选自满足以下条件的整数 0 \leq S \leq T - D。也就是说,休息时间完全适合工作时间内。柜台在非休息期间开放 [0, S) \cup [S+D, T).

有 N 希望使用柜台的顾客。最初, i第一个客户(1 \leq i \leq N) 仅在该时间段内访问计数器 [L_i, R_i)。的条件为 i第一个客户的程序 不 填写的是他们的停留期限 [L_i, R_i) 完全包含在休息期内 [S, S+D),即 S \leq L_i 和 R_i \leq S+D 按住。换言之,如果停留期间内至少存在一次柜台开放的时间,则流程完成。

高桥给出 Q 操作按顺序进行。有两种类型的操作:

  • 更新操作 (1 i L R): 更改停留时间 i第一位客户到 [L, R)。这一变化反映在所有后续操作中。可以对同一客户执行多次更新操作,并且最近的更改始终有效。
  • 查询操作 (2): 根据所有顾客当前的停留时长,确定休息开始时间 S 最大限度地减少未办理手续的顾客数量。如果有多个这样的 S,输出最小的一个。

约束

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq T
  • 1 \leq Q \leq 10^5
  • N + 2Q \leq 2 \times 10^5
  • 0 \leq L_i < R_i \leq T (对于初始状态下的每个客户)
  • 用于更新操作 1 i L R: 1 \leq i \leq N, 0 \leq L < R \leq T
  • 至少一项查询操作 2 包含在 Q 操作
  • 所有输入值均为整数

输入

T N D Q
L_1 R_1
L_2 R_2
\vdots
L_N R_N
query_1
query_2
\vdots
query_Q
  • 第一行包含营业时间长度 T,客户数量 N,断裂长度 D,以及操作次数 Q,用空格分隔。
  • 以下 N 行给出了每个客户的初始停留时间。的 i这些行中的第 (1 \leq i \leq N) 包含整数 L_i 和 R_i 以空格分隔,代表停留期限 [L_i, R_i) 的 i第一个客户。
  • 以下 Q 行每行包含一个操作。每个操作都采用以下格式之一:
  • 1 i L R: 更改停留期限 i第一位客户到 [L, R).
  • 2:执行查询操作。

输出

每次查询操作输出一行 给出 2 (输出行数等于查询操作数)。

在每一行上,输出最小的中断开始时间 S 表示未办手续的顾客数量最少,后面是当时未办手续的顾客数量,中间用空格隔开。


示例输入 1

10 3 3 5
0 2
4 6
7 10
2
1 2 3 5
2
1 1 7 10
2

示例输出 1

1 0
1 0
0 0

示例输入 2

8 4 2 6
0 1
2 4
5 8
3 7
2
1 3 6 7
2
1 1 1 3
2
2

示例输出 2

1 0
1 0
0 0
0 0

示例输入 3

30 10 7 12
0 4
3 8
6 12
9 15
14 18
17 25
20 27
1 29
11 13
24 30
2
1 4 10 16
2
1 7 0 3
1 2 22 30
2
1 10 14 20
2
1 1 5 6
1 5 23 29
2
2

示例输出 3

4 0
4 0
1 0
1 0
12 0
12 0

示例输入 4

1000 30 120 25
0 50
20 180
100 160
150 300
250 260
270 400
390 510
500 620
610 750
740 900
880 1000
5 995
123 456
321 654
600 601
700 701
800 850
50 70
75 125
200 350
360 365
420 480
490 495
520 700
710 930
940 990
30 900
111 222
333 444
555 666
2
1 5 10 130
1 12 0 120
2
1 15 119 120
1 16 120 121
1 17 121 240
2
1 1 880 950
1 30 0 1000
2
1 8 480 500
1 9 500 510
1 10 510 520
2
1 20 100 220
1 21 221 222
1 22 222 342
2
1 3 340 460
1 4 460 580
2
1 25 0 1
1 26 999 1000
2

示例输出 4

101 0
101 0
122 0
122 0
122 0
223 0
223 0
223 0

示例输入 5

1 1 1 1
0 1
2

示例输出 5

0 1