問題一覧 > 通常問題

No.3763 Compress Pancakes

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 4
作問者 : ei1333333 / テスター : kyoprouno ei13333333
お気に入りにしたユーザー ProblemId : 13891 / 自分の提出
問題文最終更新日: 2026-10-07 18:29:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 517 (順位表) の他の問題:

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.

  1. Change the weight of the $k$-th pancake from the left to $x$.
  2. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。