mygr main()

涉及选择几个数使其异或起来最小时，若有数必选，则其一开始就异或上，后面统计答案时再贪心选择，而不是丢到线性基里面

朴素线段树 基础 # 搭配倍增求解左右横跳问题 # 同种元素只有区间第一个产生影响时，离线并删去上一个元素 优化dp # 某位歌姬的故事 加强版 树剖 典 树剖+差分的例题：# P9808 [POI 2022 ~2023R1] zbo，LCA,旧词 矩阵乘法优化 也可通过此实现更为简便的历史和 # 优化斐波那契数列求解 主席树 "半离线"的二维问题解决方案 # 利用 long long 的压空间方法 [[李超线段树]] 维护区间函数的第一方式 树套树 用于带修二维问题 # 经典dfs序转二维数点-接水果 [[线段树合并]] 单侧递归 PPT 一般单侧递归问题都可以换维扫描线 # 第一代图灵机 Trick [[非重复元素配对问题]] [[扫描线]] 问题的解决方案 区间中位数也可以用二分答案法解决，区间内仅有大小比较的找数问题，都可以用 二分答案+01赋值法解决 # HEOI2016 排序 对于区间每时刻加，加后有上限的问题，可以将所有数分为“已经爆仓”和“没有爆仓”两部分，计算出每个点经过 $a_i$ 秒会变爆仓，设上次修改时间为 $x_i$ ，当前时间为...

两种实现方式：朴素合并( $O(nlogn)$ ) 与 [启发式合并] 朴素合并例题： # [PKUWC2018] Minimax 李超树+线段树合并也是 $O(nlogn)$ 的，前提是所有直线都为全局直线(总结点数与直线数相同 $O(n)$ )

线段覆盖类问题 选最少的点，使线段盖有点：线段按右端点从小到大扫，遇到没有盖有点的线段就选中右端点。 CSP-S 2024 T2 预处理每辆车会被哪个区间的测速仪检测到，转为如上问题。 选最少的线段，使目标区间全覆盖：找到覆盖目标区间左端点且右端点最大的线段，选择该线段，缩短目标区间后重复操作。 NOIP-S 2010 T4 预处理在第一行某列放下一个蓄水厂后能使最后一行哪个区间有水，转为如上问题。 选最多的线段，使线段两两不交：线段按右端点从小到大扫，找到一个没有相交的就计入答案。 ABC225E 将 7 的两端与原点连边，形成一个角。实际上一个 7 能被看到当且仅当这个角内部没有 7，转为如上问题。 给线段最少分组，使得一个组中线段两两不交：按左端点排序，如果左端点比所有组的右端点都小，那么就新开一个组，否则加入右端点最小的组。 选最多的线段，使点覆盖数不超过限制（P3602）。 做法一：从左到右遍历每个点，如果有点超过限制就删除覆盖它的右端点最大的线段。 做法二：将线段按左/右端点升序，按右/左端点升/降序排序，能加就加。

[[对 2 取模意义下的组合数]] 组合意义 $C_{x+y}^{x}$ 可以转换为从(0,0)走到(x,y)的路径条数 当涉及到循环位移直到遇到空为止的问题时，考虑多开一个点，建环，变为判定多开的那个点是否被覆盖 座位安排 对于整个序列全局加/减，部分位置特殊变化，求最值何时变化为特定值的问题是，可以考虑直接设最值为状态而非整个序列 add 1

区间绝对众数有四种找法，你知道吗？ 二分答案，找区间内出现的数量 摩尔投票法 将序列有序后，取中间那个数，绝对众数一定是这个数 枚举每个数，将这个数所在的位置变为1，其余变为-1，找区间合大于1的区间

相关链接：[[分块]] 当出现 “与区间内数的数量相关” 的题目，一般而言使用莫队

![[计数问题选讲.pdf]] Trick 对于只关心结果而不关心中间过程的题目，可以考虑找到中间过程的代表元，此时中间过程就与结果形成双射 # Erase Balls 2D

相关链接：[[凸包]]，[[斜率优化]] [[闵可夫斯基和]]： Trick 当遇到类似…图形完全包含…图形的题目时，考虑从中间往外射线，考虑是否经过奇数个点，可以拆成分层图表示经过奇/偶次射线的情况，最后变成这两种状态间的路径问题 冲浪

我们有时候需要做 “区间染色，全局查询某颜色区间内，该颜色点的数量之和” 这样的问题 ![[Pasted image 20250216163531.png]]![[Pasted image 20250216163557.png]] 例题：# P6783 Ynoi2008 rrusq