/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
0, 1 からなる長さ N の文字列 S が与えられます。S の i 文字目を S_i とします。
Q 個のクエリを与えられた順に処理してください。
クエリは 3 個の整数の組 (c, L, R) で表されて、c の値によってクエリの種類が異なります。
- c=1 のとき : L \leq i \leq R を満たす整数 i について、S_i が
1ならば0に、0ならば1に変更する。 - c=2 のとき : S の L 文字目から R 文字目までを取り出して出来る文字列を T とする。T に含まれる連続する
1の長さの最大値を出力する。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq Q \leq 10^5
- S は長さ N の
0,1からなる文字列 - c \in \lbrace 1, 2 \rbrace
- 1 \leq L \leq R \leq N
- N, Q, c, L, R は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは次の形式で与えられる。
c L R
出力
c=2 であるクエリの個数を k として、k 行出力せよ。
i 行目には i 番目の c=2 であるクエリに対する答えを出力せよ。
入力例 1
7 6 1101110 2 1 7 2 2 4 1 3 6 2 5 6 1 4 7 2 1 7
出力例 1
3 1 0 7
クエリを順に処理すると次のようになります。
- はじめ、S=
1101110です。 - 1 番目のクエリについて、T =
1101110です。T に含まれる連続する1の中で最も長いものは、T の 4 文字目から 6 文字目からなる111なので、答えは 3 になります。 - 2 番目のクエリについて、T =
101です。T に含まれる連続する1の中で最も長いものは、T の 1 文字目あるいは 3 文字目の1なので、答えは 1 になります。 - 3 番目のクエリについて、操作後の S は
1110000です。 - 4 番目のクエリについて、T =
00です。T に1は含まれないので答えは 0 になります。 - 5 番目のクエリについて、操作後の S は
1111111です。 - 6 番目のクエリについて、T =
1111111です。T に含まれる連続する1の中で最も長いものは、T の 1 文字目から 7 文字目からなる1111111なので、答えは 7 になります。
Score : 550 points
Problem Statement
You are given a string S of length N consisting of 0 and 1. Let S_i denote the i-th character of S.
Process Q queries in the order they are given.
Each query is represented by a tuple of three integers (c, L, R), where c represents the type of the query.
- When c=1: For each integer i such that L \leq i \leq R, if S_i is
1, change it to0; if it is0, change it to1. - When c=2: Let T be the string obtained by extracting the L-th through R-th characters of S. Print the maximum number of consecutive
1s in T.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq Q \leq 10^5
- S is a string of length N consisting of
0and1. - c \in \lbrace 1, 2 \rbrace
- 1 \leq L \leq R \leq N
- N, Q, c, L, and R are all integers.
Input
The input is given from Standard Input in the following format, where \mathrm{query}_i represents the i-th query:
N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in the following format:
c L R
Output
Let k be the number of queries with c=2. Print k lines.
The i-th line should contain the answer to the i-th query with c=2.
Sample Input 1
7 6 1101110 2 1 7 2 2 4 1 3 6 2 5 6 1 4 7 2 1 7
Sample Output 1
3 1 0 7
The queries are processed as follows.
- Initially, S=
1101110. - For the first query, T =
1101110. The longest sequence of consecutive1s in T is111from the 4-th character to 6-th character, so the answer is 3. - For the second query, T =
101. The longest sequence of consecutive1s in T is1at the 1-st or 3-rd character, so the answer is 1. - For the third query, the operation changes S to
1110000. - For the fourth query, T =
00. T does not contain1, so the answer is 0. - For the fifth query, the operation changes S to
1111111. - For the sixth query, T =
1111111. The longest sequence of consecutive1s in T is1111111from the 1-st to 7-th characters, so the answer is 7.