y19m08a_p8_幽靈寶藏(Treasure) 2019年,08月,TOI, 新手同好會 {題目連結}
問題敘述
探險隊在一座廢墟中找到了傳說中的藏寶箱，當他們正要取走寶藏時，出現了傳說中的海盜幽靈，幽靈決定和探險隊的成員玩一個遊戲。
遊戲的規則如下，幽靈會先變出N個空的藏寶箱，並進行以下兩種操作共M次：
(1) 在連續的數個藏寶箱內放入S枚硬幣。
(2) 使連續的數個藏寶箱內的硬幣價值變為S倍，包括事後放入的硬幣。
當幽靈完成所有操作後，探險隊可以挑選一個寶箱帶走。請你幫探險隊找出價值最高的寶箱。
範例說明1：最後寶箱內價值為：2、5、10、10、12。
範例說明2：最後寶箱內價值為：1、6、6、6、6、1，輸出編號最小者。
評分說明本題共有三組測試題組，條件限制如下所示。每組的所有測試資料皆需答對才會獲得該組分數。
子任務1 分數10 額外輸入限制:1<=N, M <=10^2
子任務2 分數30 額外輸入限制:1<=N, M <=10^4
子任務3 分數60 額外輸入限制:1<=N, M <=10^6
每筆測試資料為M＋1列，第一列有兩個正整數N和M（1<=N, M <=10^6），代表有N個空寶箱，編號為1至N，以及M個操作。緊接著M列，每列都有四個正整數P、Q、R、S（1<=P, Q<=N），R只有兩種值1或2，當R為1時，代表幽靈在第P至Q個藏寶箱內放入了S枚硬幣，當R為2時，代表幽靈使第P至Q個藏寶箱的硬幣價值變為S倍，一個寶箱的最終價值不會超過20億。
對每筆資料請輸出一列共兩個數字，為最高價值寶箱的編號以及其價值。若有數個寶箱價值相等，請輸出編號最小者。
5 4 3 5 2 2 1 4 1 2 5 5 2 2 2 5 1 3
5 12
6 5 1 6 1 1 2 3 1 2 3 5 2 2 2 2 1 3 4 5 1 2
2 6
10 5 2 9 1 99 1 7 2 1249 5 10 2 1 5 6 1 999999 6 7 1 500000
6 1873622402
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
測資有問題，經liouzhou_101大大提醒，2020/08/27更正重評
感謝 as95624268 提醒，2021/05/05測資更正
經 rollfc 的指導，這題解法應該是
把區間增值拆解為掃描線(sweepline) 搭配 入點和出點的變化量