TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

80.8% (21/26)

Submission's AC Ratio

15.4% (41/267)

Tags

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 1

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 1

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

No. Testdata Range Score
1 0~8 11
2 9~14 17
3 15~21 21
4 0~28 51

Testdata and Limits

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