TopCoder

Thumb maxresdefault
YenSean
Hello World!

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

19.3% (17/88)

Description

「抓到了!」某處傳來激動的高昂。電腦上顯示的是盩僰麌一次又一次的AC紀錄,圍觀的眾人紛紛義憤填膺,大力的指責盩僰麌的裝弱。
「我...我怎麼可能裝弱!」盩僰麌反駁。可是法網恢恢、人贓俱獲,再怎麼抵賴,都難逃正義的魔掌。

盩僰麌與激動的民眾中間彷彿出現了一條界線,上面有$N$個點,從左至右分別為$1~N$。

盩僰麌裝弱的經驗怎麼可能只有這一次,因此他也很清楚裝弱會帶給大家的憤怒,所以早就練就了一身逃跑的絕活,每次逃跑時為了使大家摸不著頭緒,會化作很多個自己,從選定的區間瞬間衝過去,缺點就是如果在這個區間有東西會造成傷害的話,盩僰麌必須全部承受。

「抓住他!」群眾在盩僰麌面前排了$N$個屏障,在位置$i$上的威力是$a_i$。屏障會對穿越他的人造成$a_i$傷害,可是如果盩僰麌同時穿越多個威力相同的屏障的話,那些威力相同的屏障只會作用一次而已。當然,面對盩僰麌是不可以掉以輕心的,因此群眾會不定時的更動屏障的威力,以避免套路被看穿。不管屏障的威力如何改變,$1\leq a_i \leq N$永遠成立。

只有屏障的阻檔是不夠抵抗盩僰麌的,因此憤怒的眾人還不時在第$L$個屏障到第$R$個屏障間設置了一到強度為$V$的雷射光,而只有當盩僰麌嘗試逃出的區間完全涵蓋$[L, R]$的時候才會觸發並對盩僰麌造成$V$的傷害。當然,由於不同的雷射光會互相的干擾,因此一個點同時只會是一道雷射光的左界(注意到雷射光部份重疊是可以的,例如$[1, 4]$與$[2, 5]$並不互相干擾)。

心急的盩僰麌在看到眼前的障礙慢慢加劇的同時,開始擔心自己逃跑的可能性,親自嘗試太危險了,於是他不時請你幫他估計若這個時刻從$[L, R]$區間中逃跑的話,總共將承受多少傷害。

Input Format

輸入第一行包含正整數$N,Q$,代表界線的長度以及事件發生的次數。
接著一行有$N$個正整數$a_i$,代表一開始每個屏障的威力。
接著$Q$行,每行代表一個事件。
若為1 p v,則位置$p$的屏障威力被改為$v$。
若為2 L R V,則群眾在第$L$到第$R$的屏障間設置了強度為$V$的雷射光,保障之前沒有左界在$L$的雷射光。
若為3 L,則左界在$L$的雷射光被移除,保障之前有一個左界在$L$的雷射光。
若為4 L R,則盩僰麌請你估計若此時從$[L, R]$逃跑的話會受到多少傷害。

對於所有測資,$N,Q\leq 10^ 5, 1\leq a_i \leq N, 1\leq L, R\leq N, V\leq 10^ 6$。保證至少有一個詢問。

子任務(測資)額外限制分數
1(0~8)$N,Q\leq 5000$11
2(9~14)沒有第2及第3種事件、$N, Q \leq 5\times 10^ 4$、第$1$種操作數量不超過$10^ 4$次17
3(15~21)所有的詢問皆在操作完成之後進行21
4(0~28)無限制51

Output Format

對於每個盩僰麌的詢問,輸出總傷害量。

Sample Input

4 8
1 1 2 2
4 1 3
1 2 3
4 1 3
2 2 3 5
4 1 3
4 3 3
3 2
4 1 4

Sample Output

3
6
11
2
6

Hints

第一筆詢問$[1, 3]$,雖然威力總和是$4$,可是兩個威力為$1$的屏障只會造成$1$傷害,總傷害$3$。
第二筆詢聞$[1, 3]$,總和為$6$。
第三筆詢問$[1, 3]$,總和為$6$加上雷射光的傷害$5$,共$11$。
第四筆詢問$[3, 3]$,由於$[3, 3]$並未涵蓋$[2, 3]$的雷射光,因此總傷害只有$2$。
第五筆詢問$[1, 4]$,雖然有兩個$2$可是只計算一次,總傷害$6$。

Problem Source

Problem Set by waynetuinfor

Subtasks

For Testdata: 0 ~ 8, Score: 11
For Testdata: 9 ~ 14, Score: 17
For Testdata: 15 ~ 21, Score: 21
For Testdata: 0 ~ 28, Score: 51
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 262144
1 1000 131072 262144
2 1000 131072 262144
3 1000 131072 262144
4 1000 131072 262144
5 1000 131072 262144
6 1000 131072 262144
7 1000 131072 262144
8 1000 131072 262144
9 1500 65536 262144
10 1500 65536 262144
11 1500 65536 262144
12 1500 65536 262144
13 1500 65536 262144
14 1500 65536 262144
15 1000 262144 262144
16 1000 262144 262144
17 1000 262144 262144
18 1000 262144 262144
19 1000 262144 262144
20 1000 262144 262144
21 1000 262144 262144
22 1000 131072 262144
23 1000 131072 262144
24 1000 131072 262144
25 1000 131072 262144
26 1000 131072 262144
27 1000 131072 262144
28 1000 131072 262144