zhangxyhp

摘要： 新加的點不會影響之前的詢問，所以直接離線，先把所有點都建好。 將問題轉化為：用 \(b\) 數組減去 \(a\) 數組，得到的形如 \(1,2,3,\dots\) 的等差序列的最大長度。 考慮將兩個序列哈希，預處理出等差數列的哈希值，二分長度即可。而在樹上維護路徑數組的哈希值，可以用倍增解決。 時間 閱讀全文

摘要： 考慮一次詢問，顯然 DP，設 \(f_{u,0/1}\) 表示走路/坐船到 \(u\) 點的最小花費即可。 多次詢問，考慮維護矩陣，廣義矩陣乘，倍增處理詢問。比如對于一條順流的邊 \(i\)，可以構造矩陣： \[\begin{bmatrix} a_i&L+a_i-z_i\\ a_i&a_i-z_i 閱讀全文