問題：詢問樹上兩點路徑和，支援修改（所以不能倍增）。 HLD: $O(\log^2 n)$詢問，$O(\log n)$修改 :::info 重子樹：點數量最多的子樹（如果都一樣則選任意個） 輕子樹：不是重子樹的其他子樹 輕邊：連接輕子樹的邊 重邊：連接重子樹的邊 重鍊：一條連續的重邊 LCA(a, b)：a,b的最小共同祖先

單調棧（monotonic stack） 建立一個stack，存pair：{值, 位置} 從左到右，每次pop stack直到最高元素比自己大（目前位置減掉頂端，就是從當下往後數第一個比自己大的位置） 原因：如果目前值比stack的頂還大，那目前的值也一定比小於stack頂端的值還大（也就是前面步驟所pop掉的）。但卻不知道會不會大於stack頂端的值還大，所以要pop直到比自己還大。 $O(2n) = O(n)$ 一個點最多走兩次 最佳化：二分搜（$O(n+logn)$） int main() { ios_base::sync_with_stdio(false);

一般 初始程式 簡易版vimrc common mistake polygon出題流程 數論 (矩陣)快速冪 輾轉相除法 模逆元

用來算區間和，以及修改區間值 令一序列為$A_1, A_2, ..., A_n$，其差分$D_i$為$A_i-A_{i-1}$ 求差分序列的前綴和即為原序列($A_{i-1}+(A_i-A_{i-1})=A_i$) 如果要在$A_l$到$A_N$全部加上$x$，只需要在$D_l$加上$x$，再求其前綴和就可以了，因為在$D_l$~$D_n$的前綴和都會包含到$D_l$(前綴和是由左往右)。 相同的如果只要在$[l, r]$加$x$，就在$D_l$加$x$，$D_r$減$x$，所以前綴和在$D_l$加了$x$後，又在$D_r$減掉$x$而恢復原來數字。 int n, m; // n:length of array m:amount of modify cin >> n >> m; vector<int> val(n+2, 0); rep(0,m){

模板 struct point{ ll x, y; point operator+(point p1){ return point{x+p1.x, y+p1.y}; } point operator-(point p1){ return point{x-p1.x, y-p1.y}; }

https://tioj.ck.tp.edu.tw/problems/1253 一個強者物質能消滅整列或整行，也就是一個x或y 所以把皮皮的x, y座標互相連成二分圖，而目標就是把每條線都涵蓋到（也就是最小點覆蓋）假設有(a, b), (a, c), (a, d)這些皮皮，這樣圖就是左邊的x=a連三條分別到y=b,c,d。所以如果選x=a，擇三條線都會覆蓋到（aka三個皮皮都消滅），成為最小點覆蓋。但如果選y=b，只有一條a - b的線被覆蓋到。 已知二分圖最大匹配=二分圖最小點覆蓋 #include <bits/stdc++.h> #define EB emplace_back #define vci vector<int>

A. 電研社的工作 每天選一個人放假組合數=每天可以放假的人數相乘 subtask 1 所有人每天都可以放假，所以答案$=k^n$ $O(n\times k)$ full score

problem setter: 賴冠澐，黃博崇 pA. IF倍倍數我 送分題 出題者:黃博崇 照題目做就好了 AC code

statement，選english，以下是配分的範例 \begin{center} \begin{tabular}{ | c | c | c | } \hline \bf{子題} & \bf{限制} & \bf{分數} \\ \hline $1$ &原題 & $100$ \\ \hline \end{tabular} \end{center}

https://zerojudge.tw/ShowProblem?problemid=a445 處理disjoint set(有向圖)disjoint set - 互不相連的群組，ex下圖 (https://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Disjoint_sets.svg/330px-Disjoint_sets.svg.png) 初始個點指向自己 find() - 查詢元素屬於哪個集合找到自己指向的元素，直到自己指向的是自己，就是那一組disjoint set的代表 ex: p[5]=2, p[2]=1, p[1]=1 -> return 1 可以邊查詢邊壓縮路徑，縮短後續查詢時間

A. 史考特序列 :::spoiler subtask 1 用個set維護 用陣列的話比較麻煩，如果想要快速的把陣列裡重複的刪掉可以用以下 sort( vec.begin(), vec.end() ); vec.erase( unique( vec.begin(), vec.end() ), vec.end() ); ::: #include<bits/stdc++.h>

:::info 有向無向皆可 ::: dijkstra 邊的權重不能為負 有n個點，設s為起點，$dis[v]$代表s到v的最點距離，$weight[a][b]$為a到b的權重，$done[v]=1$代表點v已走過, $parent[v]$是v的上一個點$dis[s]=0$，其餘為無限大 done皆為0 步驟：

埃拉托斯特尼篩法 從小到大，把沒被標記的數中所有的倍數都標記為非質數，而當讀到的數已被標記就跳過 :::success ex : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ::: 1非質數也非合數，直接畫掉 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

void match(vector<int> &z, string s){ int len=s.size(); z[0]=0; int l=0, r=0; rep(i,1,len){ if(i<=r) z[i]=min(z[i-l], r-i+1); while(i+z[i]<len && s[z[i]] == s[i+z[i]]) z[i]++; if(i+z[i]-1>r) l=i, r=i+z[i]-1; } }

https://tioj.ck.tp.edu.tw/problems/2043 樹dp 如果跟節點度數>1，那一定是從葉節點往上拔。事實上根節點度數=1也一樣從下面拔就好，因為我們會枚舉以每個點為根所形成的樹，如此就會發現不用擔心少算從根節點拔的情況了(因為那相當於以其它為根由下往上拔)。 如此樹dp的狀態就都一樣了，dp[v]代表把v的子樹都拔完的方法樹(v最後拔)。 v下面的子樹不能亂拔一通，ex:如果要拔掉某一個child，就要先把那個child下的子樹都拔完才能拔自己。但如果是不同子樹就可以交叉亂拔 這時候會發現這其實很像高一下排列組合經典題型，"甲~戊中，丙一定要在甲、乙後面的排列數"。而這個的做法就是把甲乙丙都當作同一個東西做排列，然後再把甲乙隨機排列(2!)。 轉移：就照著上述的排列組合題型解法

https://tioj.ck.tp.edu.tw/problems/1090 很像joi本選某一題，很久以前看過但當時不會，然後現在也忘了哪一題了qq 簡單來說就是設定他的左右界以及他停在哪裡，所以可以定一個dp狀態為： dp[i][j][0/1] = 吃掉i到j之間的蘋果(假設蘋果已排序)，並且停留在左邊或右邊(分別是0/1) 轉移：

算法 講師介紹 賴冠澐 - apcs 5/5 orz 課程介紹 適合已有程式語言基礎，並且有興趣參加程式競賽，或研究資訊科學的同學

用0, 1代表一個物件選或不選的狀態，壓縮成二進位集合，所以可以同時代表多個物件的01的狀態 位元操作 在k位元新增1：n | (1<<k) 在k位元刪除1：n ^ (1<<k) c460: 3. 軍隊部署 https://zerojudge.tw/ShowProblem?problemid=c460

一個二分圖中，可以用邊兩兩配對的最大匹配數 最小點覆蓋=最大匹配 最大獨立集=n-最大匹配 如果一張圖可以分成兩群，而這兩群的邊都是連到另一群的，也就是不會連到自己 Augmenting Path Algorithm :::info 交錯路徑：一條路徑中，已配對的邊和沒配對的邊相互交錯連接 增廣路徑：一個交錯路徑，但是頭尾都是未配對的邊

https://judge.tcirc.tw/ShowProblem?problemid=d088 轉移很明顯就是往前找一個最大的dp[i]且i符合題意（中間有隔離） 要找到中間有更高點的轉移點，可以用單調隊列。觀察單調隊列會發現，所有之前被pop掉的點都是可以轉移的地方(不包括目前這個點pop掉的)，如下圖黑線範圍 0到x1中間有x1作為高點，x1到x2中間有x2作為高點，而x2到x3中間有x4作為高點 但是x1, x2, x3和x3-x4中間就沒有高點了 所以我們可以開一個線段樹，預設都為0，在維護單調對列同時把pop掉的dp值update到線段樹，然後目前的dp就是0到單調對列中第一個比他高的位置(二分搜來找)的區間最大值。 好像不用線段樹xd