Description

給你一個長度為 $N$ 的序列 $a_0,a_1,\cdots,a_{N-1}$,請你實作 Input Format 中提到的四種操作或詢問。

Input Format

本題沒有輸入,如果你輸入了任何東西,可能會導致各種不可預期的結果。

#include "lib2294.h"之後實作下列五個函數:

  1. void init_array(int N);:評測程式會在一開始呼叫這個函數,代表初始化一個長度為 $N$、全部為 0 的序列。這個函數在一次執行中只會被呼叫一次,之後將會多次呼叫其餘四個函數。
  2. void add_range(int L, int R, int x);:代表要將 $a_L,a_{L+1},\cdots,a_{R-1}$ 全部加 $x$。保證 $|x|\leq 10^ 9$,且操作後序列的值皆會介於 0 到 $10^ 9$ 之間。
  3. void set_range(int L, int R, int x);:代表要將 $a_L,a_{L+1},\cdots,a_{R-1}$ 全部設為 $x$。保證 $0\leq x\leq 10^ 9$。
  4. int sum_range(int L, int R);:這個函數必須回傳當前 $a_L+a_{L+1}+\cdots+a_{R-1}$ 除以 $2^ {31}$ 的餘數
  5. int max_range(int L, int R);:這個函數必須回傳當前 $\max(a_L,a_{L+1},\cdots,a_{R-1})$ 的值。

對於後面四種操作,保證 $0\leq L<R\leq N$。

對於所有測資:

  • $1\leq N\leq 2\times 10^ 6$
  • 一次執行中呼叫後面四種操作的總次數 $Q\leq 2\times 10^ 6$。

對於 100 分的測資,$N,Q\leq 5\times 10^ 5$。

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

對於所有測資,若你的程式執行時間為時限的 $x$ 倍($0\leq x\leq 1$),該筆測資的分數為 $A\times (p+qf(x))$,其中 $A$ 為該筆測資標示的分數、$p,q$ 為各測資敘述上標示的常數,並給定常數 $a=0.5,b=0.25$,

\[f(x)=\left(s(x) \frac{(b x)^ a - b^ a}{(b x)^ a - 1.1x^ a}+\big(1-s(x)\big)\left(1-\frac{x^ 2}{2}\right)\right)\]

\[s(x)=\begin{cases}x, & x\in\{0,1\} \\ \frac{1}{1+\exp\left(\frac{8a}{b}\cot\left(\pi x^ {-\frac{\ln2}{0.1+\ln b}}\right)\right)}, & \text{otherwise}\end{cases}\]

你只需要知道 $f(0)=1,f(1)=0$,且 $f(x)$ 嚴格遞減就可以了。不過如果想要詳細了解這些函數在幹嘛的話,可以參考這個連結

Sample Input 1

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
10 6
4 4 8
1 3 6 4
2 5 10 3
2 1 2 7
3 0 9
4 3 7

Sample Output 1

注意:本題沒有輸出,本輸入為提供測試標頭檔(參見Hints)使用。
0
27
4

Hints

這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受以下輸入,數字間皆以空白分隔:
第一行:$N,Q$
接下來 $Q$ 行可以是下列四種之一,分別對應四種操作/詢問:
1. $1,L,R,x$:add_range(L, R, x)
2. $2,L,R,x$:set_range(L, R, x)
3. $3,L,R$:sum_range(L, R)
4. $4,L,R$:max_range(L, R)

對於每次 sum_rangemax_range,測試標頭檔會輸出一行包含你的函數回傳的值。

Problem Source

TIOJ 終極壓常數大賽 pC

Subtasks

No. Testdata Range Constraints Score
1 0 $p=1,q=0.2$ 70
2 1 $p=1,q=0.2$ 30
3 2 $p=0,q=1$ 120
4 3 $p=0,q=1$ 60
5 4 $p=0,q=1$ 110
6 5 $p=0,q=1$ 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1
1 2000 524288 65536 2
2 2000 524288 65536 3
3 2000 524288 65536 4
4 2000 524288 65536 5
5 2000 524288 65536 6