线段树优化建图

介绍 线段树优化建图用于解决图中边数过多,不能直接建的问题。 直接看例题: 例1 CF786B. Legacy 题意 给定 $n$ 个点的有向带权图,初始状态下图中没有边。给定 $q$ 个操作

笛卡尔树

定义 笛卡尔树是一种二叉树,每一个结点由一个键值二元组 $(k,v)$ 构成。 性质 $k$ 满足 BST 的性质 $v$ 满足 min-heap 的性质。 如果笛卡尔树的 $k,v$ 值确定,且 $k$ 互不相同,$v$ 互

整体二分

介绍 整体二分是一种思想,用于同时二分多组询问,在题目满足以下条件时可以用: 有多组询问,每组询问可以通过二分解决。 询问离线。 询问之间互相独立。

线性筛

介绍 线性筛不仅能用 $O(n)$ 求出每一个数是否为质数,它还能求出每一个数的因数数量,因数和,甚至更加general的除数函数,莫比乌斯函数等等。 总结来

NAC2023 Training Camp Day2

A. Fair Bandwidth Sharing 题意 给定 $n$ 个区间 $[l_i, r_i]$,并且给定 $n$ 个权值 $d_i$,和一个常数 $t$。 定义 $y_i = t \frac{d_i}{\sum\limits_{j=1}^n d_j}$。 求一组 $x_i$,使得满足以下所

随机化

构造题的应用 在 $n$ 较小时,确定一个随机数的seed mt19937 rng(SOME_SEED);,如果在本地成功跑出来结果,就直接把这个seed交上去,这样

CodeSprint UCLA 2023

L. Blooper Game 题意 给定 $n$ 个概率 $S_1, S_2, …, S_n$,同时给定一个实数 $P \in (0,1)$。 现在有 $L$ 次操作机会,每次操作可以选择一个 $S_i$,让 $S_i = (S_i)

Universal Cup 15 (Hangzhou)

L. Barkley 题意 给定长度为 $n$ 的数组 $a_i$,有 $q$ 个询问,每次询问为 $l~r~k$ 回答在 $[l,r]$ 这个区间内,可以去掉至多 $k$ 个数后,得到的最大 gcd 是多少? 其中,$n \leq 10^5, q

线段树分治

介绍 线段树分治一般用于处理一些 “只存在/不存在 权值为 $w$“,或者 ”某个特定时间点” 对应状态的问题。 原理是在线段树上进行 DFS,进入 DFS 时加入