zhangxyhp

摘要： 一、前言 在今年 NOIP 前學習了 FHQ-Treap（一種平衡樹），現在來記一記。 二、定義 Treap=tree+heap。具體的說，Treap 所維護的值滿足二叉搜索樹的性質，另一個變量優先級滿足堆的性質。優先級一般使一個隨機數，這使得樹的高度保持在 \(O(\log n)\) 水平，二叉搜 閱讀全文

摘要： 首先將枚舉原排列中的區間轉化為枚舉值域上的區間。 從小往大對 \(r\) 掃描線，對于每個 \(l\in[1,r)\) 維護將 \([l,r]\) 在原排列中最少要分成多少段。顯然只有 \(1\) 或 \(2\) 段才會產生貢獻。那么我們用線段樹維護值域上的每個 \(l\) 的最小段數，并維護值域區 閱讀全文

摘要： 看到“回到 \(x\) 后的狀態”，顯然考慮可持久化線段樹。記開燈的為 \(1\)，關燈的為 \(0\)，對于每個詢問只需去查某些點的權值和即可。 考慮怎么將符合條件的點轉化為區間。詢問的是同一深度的點，可以考慮 bfs 序。考慮如果 \(y\) 是奇數，顯然答案為 \(0\)；否則詢問的點就是 \ 閱讀全文

摘要： A. 【模板】線段樹分裂 首先想到了 FHQ-Treap，但是合并的時候還需要滿足大小順序，不太好搞。考慮權值線段樹。 \(1\) 到 \(4\) 操作都是比較常規的。對于 \(0\) 操作，在 \(p\) 的線段樹上將 \([x,y]\) 這個區間拆成 \(O(\log n)\) 個區間，賦給新的 閱讀全文

摘要： A. Alice 和璀璨花 做法和正常 LIS 類似。設 \(dp_{i,j}\) 表示在前 \(i\) 個中選 \(j\) 個的最小結尾顯然對于相同的 \(i\)，\(dp\) 值單調遞增。二分出 \(dp_{i-1}\) 中第一個 \(\ge i\) 的位置 \(k\)。對于 \([0,k-1] 閱讀全文

摘要： 新加的點不會影響之前的詢問，所以直接離線，先把所有點都建好。 將問題轉化為：用 \(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 閱讀全文

摘要： 設 \(f_{u,i}\) 表示 \(u\) 接受 \(i\) 的信號，\(u\) 的子樹內的答案。那么可以枚舉 \(u\) 的兒子 \(v\) 接受信號的節點來轉移。注意當 \(v\) 也枚舉到 \(i\) 時要減去重復的 \(k\)。 考慮構造方案，設 \(ans_u\) 表示答案。首先可以求出 閱讀全文

摘要： A. Minimum spanning tree for each edge 先建出最小生成樹，對于樹邊答案就是最小生成樹，對于非樹邊就從兩個端點的路徑上刪掉權值最大的即可。 證明：在這個環中，首先強制選了這條邊，然后按照從小到大的順序選邊，則一定不會選到刪掉的那條邊。 Code #include< 閱讀全文

摘要： 分塊，設塊長為 \(B\)，預處理 \(f_{l,r,x}\) 表示僅考慮 \([1,l]\cup[r,\frac{n}{B}]\) 中的玩具，花 \(x\) 元的最大愉悅度。詢問時向 \(f_{bel_l-1,bel_r+1}\) 中加入 \(l\) 和 \(r\) 所在塊內的玩具即可。\(bel 閱讀全文