【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)