Description

燒雞覺得owl不會出題

燒雞覺得owl不會出題

燒雞覺得owl不會出題

燒雞覺得owl不會出題

燒雞覺得owl不會出題

於是燒雞選了一群能力比 $owl$ 強很多的社員,讓他們出一些題目給燒雞,燒雞對每個題目會有一個滿意度 $h_{i}$ 。
有些社員有時候會覺得自己原本出的題目很難讓燒雞滿意,所以他會更改自己給燒雞的題目。
而燒雞也有可能覺得自己的標準太低了,所以他會動態調整對題目的滿意度。

給定燒雞對於每個人的題目的滿意度,接著會有以下三種操作:

  1. 將給定區間 $[l, r]$ 中所有人的題目滿意度改為區間 $[l, r]$ 中滿意度最大者(部分社員們共同繳交了目前能讓燒雞最滿意的題目)。
  2. 將 $[l, r]$ 區間中每個人的題目滿意度 $h_{i}$ 加上 $k$ (燒雞可能覺得自己標準太高了,於是將部分社員的分數調高)。
  3. 詢問目前 $[l, r]$ 之中燒雞對所有題目的滿意度平均值是否至少為 $k$ ,如果是,燒雞會很開心。

Input Format

第一行有兩個數字 $ n $ 和 $ q $ ( $ 1 \le n,q \le 2 \times 10 ^ 5 $ ),代表有多少社員參加出題與接下來有多少問題
第二行有 $n$ 個整數,第 $i$ 個整數 $h_{i} (0 \le h_{i} \le 10 ^ 9)$ 代表燒雞對每個人一開始出的題的滿意度。
接下來有 $q$ 行,有 $q$ 個問題,每個問題有一行,對於第 $i$ 個問題,會先有一個整數 $qt_{i}$ ( $1 \le qt_{i} \le 3$ )代表問題的種類,接下來會根據問體種類有一些整數。
若 $qt_{i}=1$ ,則接下來有兩個整數$ l_{i}, $ $ r_{i} $ ( $1 \le l_{i} \le r_{i} \le n$ )。
若 $qt_{i}=2$ ,則接下來有三個整數$k_{i},$ $ l_{i}, $ $ r_{i} $ ( $1 \le k_{i} \le 10 ^ 8,$ $1 \le l_{i} \le r_{i} \le n$ )。
若 $qt_{i}=3$ ,則接下來有三個整數$k_{i},$ $ l_{i}, $ $ r_{i} $ ( $1 \le k_{i} \le 3 \times 10 ^ {13}$, $1 \le l_{i} \le r_{i} \le n$ )。
意義請參考題敘

Output Format

對於每個問題種類為 $3$ 的詢問,輸出一行包含一個字串”Yes”或”No”(皆不含引號),代表當時情況能不能讓燒雞開心。

Sample Input 1

3 5
6 1 1
3 5 1 2
1 1 2
3 5 1 2
2 2 1 3
3 2 1 3

Sample Output 1

No
Yes
Yes

Hints

Problem Source

TopCoder

User's AC Ratio

100.0% (2/2)

Tags

Problem Setter

Created by owl

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536
20 1000 65536 65536
21 1000 65536 65536
22 1000 65536 65536
23 1000 65536 65536
24 1000 65536 65536
25 1000 65536 65536
26 1000 65536 65536
27 1000 65536 65536
28 1000 65536 65536
29 1000 65536 65536
30 1000 65536 65536
31 1000 65536 65536
32 1000 65536 65536
33 1000 65536 65536
34 1000 65536 65536
35 1000 65536 65536
36 1000 65536 65536
37 1000 65536 65536
38 1000 65536 65536
39 1000 65536 65536
40 1000 65536 65536
41 1000 65536 65536
42 1000 65536 65536
43 1000 65536 65536
44 1000 65536 65536
45 1000 65536 65536
46 1000 65536 65536
47 1000 65536 65536
48 1000 65536 65536
49 1000 65536 65536
50 1000 65536 65536
51 1000 65536 65536
52 1000 65536 65536
53 1000 65536 65536