No.3763 Compress Pancakes
タグ : / 解いたユーザー数 4
作問者 :
ei1333333
/ テスター :
kyoprouno
ei13333333
Problem Statement
$N$ pancakes are lined up in a row. The weight of the $i$-th pancake from the left is $A_i$.
Kaguya can perform the following operation any number of times.
- When $2$ adjacent pancakes both have weight $x$, remove those $2$ pancakes and place $1$ pancake of weight $2x$ at the position where they were.
Process the following $Q$ queries in the given order.
- Change the weight of the $k$-th pancake from the left to $x$.
- Take out the $l$-th through $r$-th pancakes from the left, keeping their order, and determine whether they can be turned into exactly $1$ pancake by performing the above operation $0$ or more times.
Note that the operation is not actually performed in this query, and the row of pancakes does not change.
Constraints
- $1 \leq N, Q \leq 3 \times 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq k \leq N$
- $1 \leq x \leq 10^9$
- $1 \leq l \leq r \leq N$
- There is at least $1$ query of type $2$.
- All input values are integers.
Input
$N$ $Q$
$A_1$ $A_2$ $\cdots$ $A_N$
$\mathrm{Query}_1$
$\mathrm{Query}_2$
$:$
$\mathrm{Query}_Q$
Each $\mathrm{Query}_i$ is given in one of the following formats.
$1$ $k$ $x$
$2$ $l$ $r$
Output
Print the answers to the queries of type $2$ in the given order, separated by newlines.
For each query, print Yes if the pancakes can be turned into exactly $1$ pancake, and No otherwise.
Sample
Sample 1
Input
4 4 1 1 1 1 2 1 4 1 2 2 2 1 3 2 2 4
Output
Yes No Yes
In the $1$st query, the weights of the pancakes in the interval $[1, 4]$ are $(1, 1, 1, 1)$. Performing the operations in the order $(1, 1, 1, 1) \to (2, 1, 1) \to (2, 2) \to (4)$ turns them into $1$ pancake.
In the $2$nd query, the weights of the pancakes become $(1, 2, 1, 1)$.
In the $3$rd query, the weights of the pancakes in the interval $[1, 3]$ are $(1, 2, 1)$. They cannot be turned into $1$ pancake.
In the $4$th query, the weights of the pancakes in the interval $[2, 4]$ are $(2, 1, 1)$. Performing the operations in the order $(2, 1, 1) \to (2, 2) \to (4)$ turns them into $1$ pancake.
Sample 2
Input
5 5 3 3 6 2 24 2 1 1 2 1 3 2 1 5 1 4 12 2 1 5
Output
Yes Yes No Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。