E - Optimization of Break Time Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、半開区間 [0, T) で表される営業時間帯に窓口の担当をしています。時刻は整数で扱います。

高橋君は、営業時間中に連続する長さ D の休憩をちょうど 1 回取らなければなりません。休憩の開始時刻を 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 が成り立つことです。言い換えると、滞在時間帯のうち窓口が開いている時刻が 1 つでもあれば手続きは完了します。

高橋君に対して、Q 個の操作が順に与えられます。操作は以下の 2 種類です。

  • 変更操作（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 個の操作の中に 1 つ以上含まれる
  • 入力はすべて整数である

入力

T N D Q
L_1 R_1
L_2 R_2
\vdots
L_N R_N
query_1
query_2
\vdots
query_Q
  • 第 1 行には、営業時間の長さ T、客の人数 N、休憩の長さ D、操作の個数 Q がスペース区切りで与えられる。
  • 続く N 行には、初期状態での各客の滞在時間帯が与えられる。このうち i 行目（1 \leq i \leq N）には、i 番目の客の滞在時間帯 [L_i, R_i) を表す整数 L_i, R_i がスペース区切りで与えられる。
  • 続く Q 行には、操作が 1 行に 1 つずつ与えられる。各操作は次のいずれかの形式である。
  • 1 i L R：i 番目の客の滞在時間帯を [L, R) に変更する。
  • 2：質問操作を行う。

出力

質問操作 2 が与えられるたびに 1 行出力してください（出力は質問操作の回数だけ行われます）。

各行には、手続きが完了しない客の人数を最小にする最も小さい休憩開始時刻 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

Score : 466 pts

Problem Statement

Takahashi is in charge of a service counter during business hours represented by the half-open interval [0, T). Time is handled as integers.

During business hours, Takahashi must take exactly one continuous break of length D. If the break starts at time S, then the break period (when the counter is closed) is the half-open interval [S, S+D). S is chosen from integers satisfying 0 \leq S \leq T - D. That is, the break fits completely within business hours. The counter is open during the non-break period [0, S) \cup [S+D, T).

There are N customers who wish to use the counter. Initially, the i-th customer (1 \leq i \leq N) visits the counter only during the time period [L_i, R_i). The condition for the i-th customer's procedure to not be completed is that their stay period [L_i, R_i) is completely contained within the break period [S, S+D), that is, S \leq L_i and R_i \leq S+D hold. In other words, if there exists at least one time within the stay period when the counter is open, the procedure is completed.

Takahashi is given Q operations in order. There are two types of operations:

  • Update operation (1 i L R): Change the stay period of the i-th customer to [L, R). This change is reflected in all subsequent operations. Multiple update operations may be performed on the same customer, and the most recent change is always in effect.
  • Query operation (2): Based on the current stay periods of all customers, determine the break start time S that minimizes the number of customers whose procedures are not completed. If there are multiple such S, output the smallest one.

Constraints

  • 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 (for each customer in the initial state)
  • For update operations 1 i L R: 1 \leq i \leq N, 0 \leq L < R \leq T
  • At least one query operation 2 is included among the Q operations
  • All input values are integers

Input

T N D Q
L_1 R_1
L_2 R_2
\vdots
L_N R_N
query_1
query_2
\vdots
query_Q
  • The first line contains the business hours length T, the number of customers N, the break length D, and the number of operations Q, separated by spaces.
  • The following N lines give the initial stay periods of each customer. The i-th of these lines (1 \leq i \leq N) contains integers L_i and R_i separated by a space, representing the stay period [L_i, R_i) of the i-th customer.
  • The following Q lines each contain one operation. Each operation is in one of the following formats:
  • 1 i L R: Change the stay period of the i-th customer to [L, R).
  • 2: Perform a query operation.

Output

Output one line each time a query operation 2 is given (the number of output lines equals the number of query operations).

On each line, output the smallest break start time S that minimizes the number of customers whose procedures are not completed, followed by the number of customers whose procedures are not completed at that time, separated by a space.

Sample Input 1

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

Sample Output 1

1 0
1 0
0 0

Sample Input 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

Sample Output 2

1 0
1 0
0 0
0 0

Sample Input 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

Sample Output 3

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

Sample Input 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

Sample Output 4

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

Sample Input 5

1 1 1 1
0 1
2

Sample Output 5

0 1