laoshan-plus

摘要： 替罪羊樹 平衡樹的一種。其特點是采用 “摧毀—重建” 的方法維護 BST 的平衡。 具體而言，當我們發現樹上有一棵子樹不平衡了，就摧毀它，然后重新建一棵平衡的子樹。 不平衡率 我們定義不平衡率 \(\alpha\in[0.5,1]\) 為：一棵以 \(u\) 為根的子樹，若其左子樹或右子樹占比大于 閱讀全文

摘要： 閱讀全文

摘要： 線性基 定義 競賽中一般用到的都是異或空間線性基。線性基可以看作針對一個數集 \(S\) 而產生的新集合，滿足線性基中的任意數能產生的異或和的種類數和原集合能產生的異或和的種類數相同，且線性基的大小最小。 由此可以得出線性基中的幾條性質（記線性基為 \(P\)）： 等價性。在原集合 \(S\) 上進 閱讀全文

摘要： Burnside 引理和 Polya 定理 群論基礎 若集合 \(S\ne\varnothing\) 和 \(S\) 上二元運算 \(\cdot\) 構成的代數結構 \(G(S,\cdot)\) 滿足以下性質： 封閉性：\(\forall a,b\in S\)，\(a\cdot b\in S\)； 閱讀全文

摘要： K-D Tree 簡介 K-D Tree 是一種能夠維護多維數據的二叉樹。一般來說，競賽中用到的都是 2-D Tree，即維護二維數據，比如平面上的點的數據。 K-D Tree 能解決的問題用很多其他的數據結構也能解決，比如 CDQ 分治、樹套樹，抑或是一些計算幾何知識。因為 K-D Tree 在 閱讀全文

摘要： 線段樹綜合 線段樹 Pro Max。 前置知識：權值線段樹，動態開點線段樹。這兩個東西是相輔相成的，到現在應該很熟練。其中權值線段樹可以維護數字的出現次數相關信息，動態開點線段樹則是解決值域過大帶來的問題，或者是要開多個線段樹之用。 線段樹分裂 前置知識：線段樹合并。那么有合并就有分裂，線段樹分裂一 閱讀全文

摘要： 奇技淫巧。 閱讀全文

摘要： 可持久化數據結構 首先需要知道，何謂可持久化？具體而言，就是對每次操作保留一個歷史版本，同時可以基于其中一個歷史版本進行操作，且復雜度在可接受范圍內。 顯然不能每次都拷貝一遍，但是利用一些性質，一些常見的數據結構都是在同樣的復雜度下做到可持久化的。 可持久化線段樹（主席樹） 其實主席樹不完全等于可持 閱讀全文

摘要： 拉格朗日插值 插值 什么是插值？插值是一種通過已知的、離散的數據點推算一定范圍內的新數據點的方法。 插值的一般形式如下： 已知 \(n\) 個點 \(P_1(x_1,y_1),P_2(x_2,y_2),\dots,P_n(x_n,y_n)\)，求 \(n-1\) 次多項式 \(f(x)\) 滿足 \ 閱讀全文

摘要： 杜教篩 積性函數 定義 定義在所有正整數上的函數稱為算術函數（或數論函數）。 若算術函數 \(f\) 滿足對于任意兩個互質的正整數 \(p\) 和 \(q\) 均有 \(f(pq)=f(p)f(q)\)，則稱該函數為積性函數。 若算術函數 \(f\) 滿足對于任意兩個正整數 \(p\) 和 \(q\ 閱讀全文