k-D Tree 是一种可以高效处理 $k$ 维空间信息的数据结构，在算法竞赛的题目中一般 $k = 2$。 建树 k-D Tree 具有二叉搜索树的形态，二叉搜索树上的每个节点都对应 $k$ 维空间内的一个点。其每个子树中的点...

Codeforces Round #647 (Div. 1) - Thanks, Algo Muse! Johnny and Contribution 傻逼模拟题，用 stable_sort 排序一下，然后判一下无解。 const int N = 5e5 + 7; int n, m, a[N], p[N], q[N]; vi e[N]; ...

AtCoder Grand Contest 037 Dividing a String 可以证明划分出来的段长度不超过 $2$，于是 $\mathcal O(n)$ DP 即可。 const int N = 2e5 + 7, inf = 1e9; int n, f[N][2]; char s[N]; int main() { ...

JOISC 2018 Day 1 道路建设 发现操作本质上是一个 $\text{access}$，LCT 维护即可，逆序对就把路径上的颜色块爬下来树状数组求就行了，时间复杂度 $\mathcal O(n \log^2 n)$。 const int N = 1e5 + 7; s...

AtCoder Grand Contest 044 Pay to Win 倒着考虑，记忆化搜索一下即可。 #define ll __int128 const int o[3] = {2,3,5}; const ll inf = 1e18; ll n, a[3], d; map<ll, ll> p; inline ll f(ll x) ...

USACO 2018 December Contest Balance Beam 单调栈求一个上凸壳即可。 卡精度，要用 __int128。 const int N = 1e5 + 7; int n; __int128 a[N]; vi s(1, 0); inline bool pd(int i, int j, int k) { ...

一些神仙的博客，没脸放到友链上所以就放这儿来。 cz_xuyixuan hzwer immortalCO Matrix67 matthew99 mcfx Menci Miskcoo nocriz OwenOwl rqy Sengxian VFleaKing yww

JOISC 2019 Day1 試験 (Examination) 裸的三维偏序模板题，$\mathcal O(n \log^2 n)$ 的 CDQ 分治即可。 const int N = 6e5 + 7; int n, m, a[N], c[N], t, ans[N]; struct P { int x, y, z, o; ...

USACO 2019 December Contest Greedy Pie Eaters 区间 dp。 考虑最后放上去的区间，必有一个位置被新覆盖了。 枚举这个位置即可，时间复杂度 $\mathcal O(n^3)$。 const int N = 307; int n, m, a[N][N...

Codeforces Round #641 (Div. 1) Orac and LCM 每个质因子考虑一下即可。 namespace shai { const int N = 1e6 + 7; int p[N], v[N], phi[N], miu[N]; inline void init(int n) { v[...