【ZJ c259】 kevin 改區間

第一篇文章ww
原題連結：https://zerojudge.tw/ShowProblem?problemid=c259
剛看到的時候覺得是經典題，但沒什麼想法
拜某建中的蔣大大傳了篇文章之後才搞懂這精湛的解法
寫完之後居然一次過了Orz 人品爆發(?

解題概念：
開一棵線段樹，維護以下：
1.總和(sum)
2.最小值(Min)
3.最小值的個數(min_count)
4.次小值(sec_min)，葉節點預設INF
5.懶標(lazy)

前4個在未修改的情況下的維護是很簡單的
關鍵在「修改值」
對於一個線段樹上的node和V取MAX，分成3個case來處理：
case 1:V<=min
　　return
case 2:V<sec_min
　　利用min_count和Min做運算後維護sum，把Min和lazy覆蓋掉後return
case 3:V>=sec_min
　　暴力往下推左右兒子

如果不觸發case 3的話，複雜度會是完美的O(QlogN)
而對於case 3的複雜度分析，考慮每次遞迴後，因為是對整個node取MAX，則數字種數必定會減少1，至多減少node的區間大小次，所以減少的次數是呈線性的，複雜度為O(NlogN)

總複雜度約為O((N+Q)logN)