시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 32 | 25 | 23 | 76.667% |
Suppose you are given an array of n entries where each array entry is either 0 or 1. For any pair (ℓ, r) such that 1 ≤ ℓ ≤ r ≤ n, [a[ℓ], a[ℓ + 1], ..., a[r]] is a subarray of the array [a[1], a[2], ..., a[n]]. An alternating subarray [a[ℓ], a[ℓ + 1], ..., a[r]] of [a[1], a[2], ..., a[n]] if a[ℓ] ≠ a[ℓ + 1] ≠ ··· ≠ a[r]. I.e., every entry in the subarray is different from its neighbors in the subarray. Since the definition of alternating subarrays only considers the entries in the subarrays, [1, 0, 1] is still an alterating subarray of [1, 1, 0, 1, 1].
In this problem, two types of operations will be applied to the given array.
Please write a program to maintain the given array. Your program must report the numbers efficiently.
The first line contains two integers n and q, indicating the length of the given array and the number of operations. The second line contain n space separated numbers a[1], a[2], ..., a[n] representing the given array [a[1], a[2], ..., a[n]]. Then q lines follow, and the i-th of them contains 3 integers ti, ℓi, ri where the i-th operation is ti ℓi ri .
For each operation of the second type, output the reported number on one line.
3 1 1 1 0 2 1 3
4
20 20 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 1 1 10 2 2 7 1 3 15 2 1 9 1 4 9 2 1 13 1 13 15 2 10 20 1 1 5 2 2 10 1 15 17 2 15 18 1 1 3 2 4 6 1 15 19 2 1 6 1 15 15 2 10 17 1 1 8 2 15 19
16 16 21 14 12 6 4 9 10 8
ICPC > Regionals > Asia Pacific > Taiwan > Taiwan Online Programming Contest > TOPC 2021 F번