隨手coding筆記 by波路特石

原題連結： http://tioj.infor.org/problems/1974 這題是一階的模考題 難度在其中應該是偏易的？ 想法在於試著枚舉其中一維度，如果能在極短的時間內求出另一維度的當前最大值就能完成。 矩形只有10^5個，左右界分開看每一維度共有2*10^5個，不難發現座標範圍10^9只是一個叫你離散化的騙局(?)，兩個維度分別真正會出現不同值域的範圍只有2*10^5種而已。 因為要枚舉其中一維度，所以這個維度(我是用x)就不需要離散化，於是先對y座標離散化。 維護y座標的最大值時，可以發現如果硬是把欲枚舉x座標的矩形加進來，對於一個固定的y座標，只要把在其上的矩形加進來最後扣掉重疊的矩形就好。 利用掃描線+線段樹跟著枚舉一起跑，維護好「扣掉重疊矩形」這個動作，就能夠O(1)查詢每個x座標的極值。 線段樹總共被修改2*n次，總共複雜度O(nlgn) 由於題目的權重不存在負值，然後我沒有發現這件事@@ 如果有負值的話還要記得額外判斷十字線有一維度完全沒射中的情況，最後和0取MAX應該才是正解。

原題連結： http://codeforces.com/problemset/problem/914/D 這題我在比賽當中想到詢問O((logn)^2)的作法，雖然壓常數後過了，可是最後還是被system test卡掉QQ 不過在賽後重送一次一模一樣的code卻過了，不知道是不是伺服器負荷量問題... 原題的詢問可以視為，詢問區間內無法被x整除的數字是否超過1個。 則考慮一個gcd線段樹，query的時候在外面開一個「無法被整除數字」的計數器。 函式裡，只要有區間能被x整除就直接return，否則就持續往詢問的區間遞迴。 如果當前node是涵蓋在詢問區間裡的： case 1: l==r(node的區間只代表一個數字) 　　因為能遞迴到這裡表示一定不能整除，計數器+1 case 2: otherwise 　　暴力往下遞迴 最後在函式的開頭補上，計數器>1就直接return。 可以觀察到，會暴力遞迴到底的次數頂多只有兩次，兩次後計數器會>1，其他的待跑函式會全部return，複雜度O(logn) 總複雜度O(N+Qlogn)(不含修改，修改約O(logn*logC)，但gcd的期望值和單點修改的常數都遠比預計的小，所以可以不用在意)

第一篇文章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)