C - Binary Search on a Segment Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 3 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

クエリを Q 個処理してください。クエリは以下の 3 種類のいずれかです。

  • 1 i x：A_i を x に変更する。
  • 2 l t：\displaystyle \sum_{i=l}^{r} A_i \geq t を満たす l 以上 N 以下の整数 r のうち、最小のものを出力する。そのような整数 r が存在しない場合は、N+1 を出力する。
  • 3 r t：\displaystyle \sum_{i=l}^{r} A_i \geq t を満たす 1 以上 r 以下の整数 l のうち、最大のものを出力する。そのような整数 l が存在しない場合は、0 を出力する。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 種類目のクエリについて、1 \leq i \leq N, 0 \leq x \leq 10^9
  • 2 種類目のクエリについて、1 \leq l \leq N, 1 \leq t \leq 10^{15}
  • 3 種類目のクエリについて、1 \leq r \leq N, 1 \leq t \leq 10^{15}
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下のいずれかの形式で与えられる。

1 i x

2 l t

3 r t

出力

2 種類目または 3 種類目のクエリを合わせた個数を q として、q 行出力せよ。j 行目には、2 種類目または 3 種類目のクエリのうち j 番目のものに対する答えを出力せよ。

入力例 1

5 8
2 1 3 0 4
2 2 4
3 5 5
1 3 1
2 2 4
3 5 5
2 4 5
3 2 4
2 1 2

出力例 1

3
3
5
3
6
0
1

1 番目のクエリでは、A_2=1 \lt 4 である一方、A_2+A_3=4 であるため、3 を出力します。

2 番目のクエリでは、A_3+A_4+A_5=7 である一方、A_4+A_5=4 であるため、3 を出力します。

3 番目のクエリでは、A は (2,1,1,0,4) に変更されます。

4 番目のクエリでは、A_2+A_3+A_4=2 \lt 4 である一方、A_2+A_3+A_4+A_5=6 であるため、5 を出力します。

5 番目のクエリでは、A_4+A_5=4 \lt 5 である一方、A_3+A_4+A_5=5 であるため、3 を出力します。

6 番目のクエリでは、A_4+A_5=4 \lt 5 であり、条件を満たす r は存在しないため、6 を出力します。

7 番目のクエリでは、A_1+A_2=3 \lt 4 であり、条件を満たす l は存在しないため、0 を出力します。

8 番目のクエリでは、A_1=2 であるため、1 を出力します。

入力例 2

1 6
0
2 1 1
3 1 1
1 1 1000000000
2 1 1000000000
3 1 1000000000
2 1 1000000000000000

出力例 2

2
0
1
1
2

Score: 3 points

Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 3 types:

  • 1 i x: Change A_i to x.
  • 2 l t: Print the smallest integer r between l and N, inclusive, that satisfies \displaystyle \sum_{i=l}^{r} A_i \geq t. If no such integer r exists, print N+1.
  • 3 r t: Print the largest integer l between 1 and r, inclusive, that satisfies \displaystyle \sum_{i=l}^{r} A_i \geq t. If no such integer l exists, print 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • For type 1 queries, 1 \leq i \leq N, 0 \leq x \leq 10^9
  • For type 2 queries, 1 \leq l \leq N, 1 \leq t \leq 10^{15}
  • For type 3 queries, 1 \leq r \leq N, 1 \leq t \leq 10^{15}
  • All numerical values in the input are integers.

Input

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

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following formats:

1 i x

2 l t

3 r t

Output

Let q be the total number of queries of types 2 and 3. Print q lines. The j-th line should contain the answer to the j-th query among those of types 2 and 3, in the order they are given.

Sample Input 1

5 8
2 1 3 0 4
2 2 4
3 5 5
1 3 1
2 2 4
3 5 5
2 4 5
3 2 4
2 1 2

Sample Output 1

3
3
5
3
6
0
1

For query 1, A_2=1 \lt 4 while A_2+A_3=4, so print 3.

For query 2, A_3+A_4+A_5=7 while A_4+A_5=4, so print 3.

Query 3 changes A to (2,1,1,0,4).

For query 4, A_2+A_3+A_4=2 \lt 4 while A_2+A_3+A_4+A_5=6, so print 5.

For query 5, A_4+A_5=4 \lt 5 while A_3+A_4+A_5=5, so print 3.

For query 6, A_4+A_5=4 \lt 5, and no r satisfies the condition, so print 6.

For query 7, A_1+A_2=3 \lt 4, and no l satisfies the condition, so print 0.

For query 8, A_1=2, so print 1.

Sample Input 2

1 6
0
2 1 1
3 1 1
1 1 1000000000
2 1 1000000000
3 1 1000000000
2 1 1000000000000000

Sample Output 2

2
0
1
1
2