出于一些原因，只有 4.21 往后的题。
LOJ6481 Visual Python++
考虑贪心。非常容易想到，从左往右扫，每次扫到一个右下角时就匹配一个在它上面但是高度差最小的左上角，如果有多个同一高度的可以不用考虑顺序，因为边界重合的情况是不合法的。
对于一种匹配方案，怎么判断它合不合法呢？我们同样考虑从左往右扫，在左边界加入线段，右边界删除。扫到一条矩形的边界 \((y_1,y_2)\) 的时候，查询当前的线段中是否存在线段 \([l,r]\)，满足 \(y_1\le l\le y_2\) 或 \(y_1\le r\le y_2\)，用一个 set 可以轻松维护。
但是这样没法判断所有的不合法情况。我们只需要将 \(x,y\) 坐标交换然后再进行一次相同的过程即可。
正确性可以通过手搓所有不合法情况来验证。
时间复杂度 \(O(n\log n)\)。
LOJ2470 有向图
一眼丁真保序回归。直接莽一个保序回归板子，可以在 \(m=n-1\) 的情况下达到 \(O(n\sqrt n \log n)\) 的优秀复杂度，可以获得 \(50\) 分。
我们考虑如何快速地解决最小权闭合子图问题。对于树的情况：我们有 DP 状态 \(f_{u,0/1}\) 表示 \(u\) 选了 \(mid/mid+1\) 时的子树内最小代价。求方案时做一遍 DFS 并贪心按照 DP 值选取即可。时间复杂度 \(O(n\log n)\)。
对于基环树的情况，我们钦定一个环上的点为根，记录 DP 状态 \(f_{u,0/1,0/1}\) 表示 \(u\) 选了 \(mid/mid+1\)，根选了 \(mid/mid+1\) 时的最小代价。对于非树边 \((root,u)\)，我们在计算到 \(f_{u,*,*}\) 时将不合法的状态赋值为 \(+\infin\) 即可。
时间复杂度 \(O(n\log n)\)。
LOJ6723 教科书般的亵渎
注意到加入随从只会是亵渎的效果越来越好，而 \(n\) 种亵渎的总触发次数是 \(O(n\ln n)\) 级别的，所以我们只需要维护每次添加随从后每个亵渎触发次数有没有增加即可。
对于参数为 \(d\) 的亵渎，发动次数是集合 \(\{\lfloor\frac{h_i}{d}\rfloor\}\) 的 \(\text{mex}-1\)，其中 \(h_i\) 是随从的血量。我们设当前参数为 \(d\) 的亵渎发动次数为 \(x_d\)，则添加一个血量在 \((dx_d,dx_d+d]\) 中的随从时，该亵渎就可以多发动一次。所以我们只要维护这些区间即可，这是简单的。
时间复杂度 \(O(n\log^2 n)\)。
LOJ3280 首都城市
首先考虑我们一定要选颜色 \(1\) 时怎么做。显然我们此时一定要选择颜色 \(1\) 虚树中所有的点，然后我们会得到一些新的颜色，然后我们又可以找到一些新的必须要选的点。具体的实现中我们可以随便选择一个颜色 \(1\) 的点为根，然后进行 BFS 过程：选颜色 \(x\) 的点之后要把其他所有颜色 \(x\) 全选完且选点 \(u\) 一定要选它的父亲。
直接暴力是 \(O(n^2)\) 的，然后我们把它修改成点分治就可以得到一个简单的 \(O(n\log n)\) 做法了。有点小细节。
LOJ6411 三角形
由于 \(r,c\) 同阶，复杂度叙述中用 \(n\) 代替 \(r,c\)。
容易想到一个 \(O(n^3)\) 的做法：预处理每个点往左上/右上/左下/右下走最多能走多少条边，枚举等边三角形横着的那条边计算答案。
考虑如何优化枚举方式，这里以正着的三角形为例，倒着的是对称的。设点 \((i,j)\) 往左上/右上分别能走 \(f(i,j),g(i,j)\) 条边，则对于左下角 \((i,j)\)，合法的右下角需 \((i,x)\) 要满足：
- \(x-j\leq g(i,j)\)
- \((i,j)\) 向右能走到 \((i,x)\)
- \(f(i,x)\geq x-j\)
对于前两个限制，实际上是确定了右下角的 \(y\) 坐标在一个区间内；第三个限制，对应着我们需要查询区间中 \(f(i,j)-j\) 大于某个值 \(x\) 的个数，容易做到 \(O(n^2\log^2 n)\)。
Baekjoon18070 Double Palindrome
先考虑把同一个串的多个拆分方式看作不同方案的情况，则答案为 \(\sum\limits_{i=1}^{n}k^{\lceil\frac{i}{2}\rceil+\lceil\frac{n-i}{2}\rceil}\)。
下面考虑分析一下有多种拆分方式的串有什么良好的性质。
我们发现：一个合法串一定可以表示为一个仅有一种拆分方式的模式串重复一遍或多遍得到的串，且表示方法唯一。这里的拆分方式包含整个串本身就是一个回文串的情况。
然后就很好搞了！显然有 \(f(x)=F(x)-\sum\limits_{d|x,d<x}f(d)\frac{n}{d}\)，其中 \(F(n)=\sum\limits_{i=1}^{n}k^{\lceil\frac{i}{2}\rceil+\lceil\frac{n-i}{2}\rceil}\)。
时间复杂度 \(O(n\log n)\)。
AGC038E Gachapon
容易想到 \(\min-\max\) 容斥：计算对于每个 \(\{1,2,\cdots,n\}\) 的子集 \(S\)，\(S\) 中第一次存在达到限定次数的数的期望轮数。
令 \(P(S)=\sum\limits_{x\in S}A_x\)。对于一个固定的 \(S\)，容易计算它的答案为 \((-1)^{|S|}\frac{P(\{1,2,\cdots,n\})}{P(S)}\sum\limits_{\{a_i\},0\leq a_i<B_i}(\sum a_i)!\prod\limits_{x\in S}(\frac{A_x}{P(S)})^{a_x}\frac{1}{a_x!}\)。
这个式子显然可以使用动态规划解决，状态中需要记录当前考虑到前 \(i\) 个数，\(P(S)=j\)，所有 \(a_x\) 的和为 \(k\) 的贡献总和。转移时暴力枚举 \(a_i\) 即可。
时间复杂度 \(O((\sum A_i)(\sum B_i)^2)\)。
SPOJ GCD Extreme
普及组题目。随便 \(O(n\ln n)\) 预处理一下就行。
Gym101404B Free Goodies
注意到第一个人一定是按照一个固定的顺序选最靠前的一个，这个条件可以转化为按照该顺序排好后，对于任意一个前缀 Jan 选择的个数都小于等于 Petra 选择的个数（如果 Jan 是先手就 \(+1\)）。
然后就可以 DP 了，\(f(i,j)\) 表示考虑前 \(i\) 个，Jan 选了 \(j\) 个的最大总和。
时间复杂度 \(O(n^2)\)。
Gym101464C Largest Empty Circle on a Segment
显然这题满足单调性，所以考虑二分。
二分出半径 \(r\) 了之后，我们可以对于每条线段处理出会使圆和该线段相交的 \(x\) 区间。具体地，我们把这条线段看成一个香肠形，或者说一个长方形和两个圆叠一起，然后分别和圆心所在的线段求交即可。
时间复杂度 \(O(n\log n)\)。
AGC008E Next or Nextnext
考虑边 \(i\rightarrow a_i\) 组成的有向图，它一定是一个基环树森林。
我们注意到，若一个基环树满足存在一个点，有至少两个非环上的点连向它，答案就为 \(0\)。
两个长度为 \(n\) 的环还可以合并，合并的方案有 \(n\) 种。一个基环树上的方案是容易计算的。然后随便乘法原理计数一下即可。
注意一个细节：长度为大于 \(1\) 的奇数的一个单环有两种方案：一步一跳和两步一跳。
时间复杂度 \(O(n)\)。
标签：log,线段,mid,笔记,亵渎,复杂度,2023.4,sum From： https://www.cnblogs.com/Kevin090228/p/17366322.html