小明の雜貨鋪

单调栈与单调队列 题意 给定一个环，判断有多少元素满足：所有以这个元素为起始的区间的和非负。(普及 +/ 提高, VJwin2C - 好消息，坏消息) Step1 断环为链 注意所需的数组范围变大，N 应改为 2*N。 123int n = read();for (int i = 1; i <= n; ++i) a[i + n] = a[i] = read(); // 断环为链for (int i = 1; i <= 2 * n - 1; ++i) s[i] = s[i - 1] + a[i]; // 前缀和 Step2 单调队列 熟知可以用前缀和表示区间之和，如区间 k~l 等于 a[l]-a[k-1]，那么要判断区间和是否为正数，只要最小前缀和是否大于前面数的和。以前缀和作为单调队列，维护单调队列是递增的，以保证留下最小的元素。 需计算 kkk 的个数，满足 ∀i∈[k,k+n], ak+ak+1+⋯+ak+n⩾0\forall i\in[k,k+n],~a_k+a_{k+1}+\dots+a_{k+n} \geqslant...

本文需要重写。 Disjoint Set Union (Uno-Find Set) 路径压缩： 1234int fa[N];inline void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }inline void uno(int x, int y) { fa[find(x)] = find(y); } 按秩合併： 123456789int fa[N], rnk[N];inline void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, rnk[i] = 1; }int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }inline...

讲解； 课件； 练习； 题解 ST Table ST 表 (Sparse Table, 稀疏表) 基于 倍增 思想，用于解决 可重复贡献问题 †^\dagger†，支持在 Θ(1)\Theta(1)Θ(1) 的时间内 区间查询，不支持在线修改。 预处理时间复杂度 Θ(nlog⁡n)\Theta(n\log n)Θ(nlogn)，查询时间复杂度 Θ(1)\Theta(1)Θ(1)。 †:^\dagger:†: 区间询问对应的运算符 ∗*∗ 满足 x∗x=xx*x=xx∗x=x 和结合律 (x∗y)∗z=x∗(y∗z)(x*y)*z=x*(y*z)(x∗y)∗z=x∗(y∗z) ，如 max⁡, min⁡, ⊕, ∣ , &, gcd⁡\max,\ \min,\ \oplus,\ |\ ,\ \&,\ \gcdmax, min, ⊕, ∣ , &, gcd 等，包括 RMQ (Range Maximum/Minimum Query) 问题和区间...

本文需要重写。 Disjoint Set Union 併查集 一些常用： 求元素 kkk 所在連通圖的元素數量 Sk={1⩽i⩽n ∣find⁡(k)=find⁡(i)}S_k=\left\{1\leqslant i\leqslant n ~\vert\operatorname{find}(k)=\operatorname{find}(i)\right\}Sk​={1⩽i⩽n ∣find(k)=find(i)}： 123for (int i = 1; i <= n; ++i) { Sk += find(k) == find(i);} 求連通圖總數 S={1⩽i⩽n ∣find⁡(i)=i}S=\left\{1\leqslant i\leqslant n ~\vert\operatorname{find}(i)=i\right\}S={1⩽i⩽n ∣find(i)=i}，至少需要 S−1S-1S−1 條線才能將所有連通圖連通： 123for (int i = 1; i <= n; ++i) { ans +=...

Unicode 中的花體字母和數字 上下标 上标字符: X⁰¹²³⁴⁵⁶⁷⁸⁹⁺⁻⁼⁽ᵃᵇᶜᵈᵉᶠᵍʰⁱʲᵏˡᵐⁿᵒᵖʳˢᵗᵘᵛʷˣʸᶻ⁾ᵝᵞᵡ 下标字符: X₀₁₂₃₄₅₆₇₈₉₊₋₌₍ₐₑₕᵢⱼₖₗₘₙₒₚᵣₛₜᵤᵥₓ₎ᵦᵧᵨᵩᵪ LETTER Bold：𝐀𝐁𝐂𝐃𝐄𝐅𝐆𝐇𝐈𝐉𝐊𝐋𝐌𝐍𝐎𝐏𝐐𝐑𝐒𝐓𝐔𝐕𝐖𝐗𝐘𝐙𝐚𝐛𝐜𝐝𝐞𝐟𝐠𝐡𝐢𝐣𝐤𝐥𝐦𝐧𝐨𝐩𝐪𝐫𝐬𝐭𝐮𝐯𝐰𝐱𝐲𝐳 Italic：𝐴𝐵𝐶𝐷𝐸𝐹𝐺𝐻𝐼𝐽𝐾𝐿𝑀𝑁𝑂𝑃𝑄𝑅𝑆𝑇𝑈𝑉𝑊𝑋𝑌𝑍𝑎𝑏𝑐𝑑𝑒𝑓𝑔ℎ𝑖𝑗𝑘𝑙𝑚𝑛𝑜𝑝𝑞𝑟𝑠𝑡𝑢𝑣𝑤𝑥𝑦𝑧 Bold...