26. 阿源的田地 4

0 Judge

Code: 0


阿源的田地 4

題目敘述

阿源終於賣完他的貨物了,一天又平安的過去了,感謝阿源的努力。 時間過得很快,又到了要種植下一季作物的時候,這次阿源種植了$n$棵果樹排成一列,我們將樹兒們依序編號為$1~n$,剛開始這些樹高度皆為$0$,這些樹非常的奇妙,當某顆樹被陽光照射$x$分鐘時,他就會長高$x$公分,而陽光一次 會照射一個區間的樹,現在阿源想隨時知道某顆樹現在長的多高,以便監控這些樹的生長狀態。 現在總共有$q$次事件,每次事件可能有兩種: 第一種為陽光照射編號$l$到$r$這個區間的樹$x$分鐘,我們會以 $1 l r x$來代表 第二種為阿源想知道編號$x$這個樹的高度(公分),我們以 $2 x$來代表 對於每個第二種事件,請輸出所詢問的樹的高度。

輸入說明

輸入的第一行包含一個正整數 $T(T\leq 10)$,代表接下來有 $T$ 個測試資料。 每筆測試資料第一行會有兩個正整數 $n(n\leq 1000000)$ 及 $q(q\leq1000000)$ ,分別代表有$n$顆樹及$q$次事件,每顆樹剛開始高度都為0。 接下來每次事件會有兩種形式。 $1 l r x$ 代表$l$到$r (1 \leq l\leq r \leq n)$ 這個區間的樹 $x(1\leq x \leq 1e9)$分鐘 $2 x$ 代表阿源想知道$x(1\leq x\leq n)$這顆樹的高度

輸出說明

對於每次第二種詢問,請輸出一個整數代表樹的高度

範例輸入

範例輸出

範例解釋

全部樹的高度一陽光照射的順序變化如下

$0,0,0,0,0,0,0,0,0,0$

$1,1,1,1,1,1,1,1,1,1$

$1,6,6,1,1,1,1,1,1,1$

$1,6,6,7,7,7,7,1,1,1$

$1,6,15,16,16,16,7,1,1,1$

$2,7,16,17,17,17,8,2,2,2$

子題一[10%]

$n \leq 1000,q \leq 1000$

子題二[10%]

$n \leq 1000,q \leq 1000000$

子題三[20%]

所有第一種事件都在第二種事件前發生

$ 子題四[40%]

$n \leq 100000,q \leq 100000$

子題五[20%]

$n \leq 1000000,q \leq 1000000$


Judge Setting

run-time limit: 20000 ms
memory limit: 100048576 byte
測資數量: 6