問題一覧 > 通常問題

No.880 Yet Another Segment Tree Problem

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : beetbeet / テスター : tubuanntubuann
7 ProblemId : 3281 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-09-07 00:06:59

問題文

要素数 $N$ の数列 $A = \{ a_1, a_2, ... , a_N \} \ $ が与えられます。

以下の 4 種類のクエリが合計 $Q$ 個与えられるので、それらを順番に処理してください。

  • $1 \ l \ r \ x$
    • 各 $i \in [l, r]$ について、$a_i$ の値を $x$ で置き換える

  • $2 \ l \ r \ x$
    • 各 $i \in [l, r]$ について、$a_i$ の値を $gcd(a_i, x)$ で置き換える

  • $3 \ l \ r$
    • $\displaystyle \max_{i \in [l, r]} a_i $ の値を出力する

  • $4 \ l \ r$
    • $\displaystyle \sum_{i \in [l, r]} a_i $ の値を出力する

入力

$N \ Q$
$a_1 \ a_2 \ \cdots \ a_N$
$query_1$
$query_2$
$\cdots$
$query_Q$

1 行目に数列の長さを表す整数 $N$ とクエリの数を表す整数 $Q$ がこの順で半角スペース区切りで与えられます。

2 行目には $N$ 個の整数が半角スペース区切りで与えられ、その内の $i$ 番目 $(1 \le i \le N)$ の整数は、初期の $a_i$ の値を表します。

続く $Q$ 行のうちの $i$ 行目 $(1 \le i \le Q)$ には、$i$ 番目のクエリが与えられます。

各クエリは

  • $1 \ l \ r \ x$
  • $2 \ l \ r \ x$
  • $3 \ l \ r$
  • $4 \ l \ r$

のいずれかの形式で与えられます。


入力は全部で $Q + 2$ 行となり、以下の制約を満たします。

  • 入力は全て整数
  • $1 \le N, Q \le 10^5$
  • $1 \le a_i \le 10^9 \ \ (1 \le i \le N)$
  • クエリ1
    • $1 \le l \le r \le N$
    • $1 \le x \le 10^9$
  • クエリ2
    • $1 \le l \le r \le N$
    • $1 \le x \le 10^9$
  • クエリ3
    • $1 \le l \le r \le N$
  • クエリ4
    • $1 \le l \le r \le N$
  • クエリ3 と クエリ4 は合計 1 つ以上存在する

出力

各クエリ3に対して、$ \displaystyle \max_{i \in [l, r]} a_i $ の値を、各クエリ4に対して、$ \displaystyle \sum_{i \in [l, r]} a_i $ の値を、それぞれ改行区切りで出力してください。

サンプル

サンプル1
入力
5 11
1 6 8 7 3
3 1 5
4 1 5
2 1 5 6
3 1 5
4 2 4
1 1 5 10
3 1 4
4 3 5
2 3 4 3
3 2 3
4 4 5
出力
8
25
6
9
10
30
10
11

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。