二分与倍增

两者的本质均基于单调性，寻找题目中具有单调性的函数关系，然后施展二分或者倍增。二分答案可以用来解决分数规划问题，三分法可以求解单峰/谷函数。同时，二分上界不确定的内容的最佳方式是倍增，通过先倍增到上界，再倍增答案来解决。

二分

一种二分写法

通过 l <= r 之类的方法的二分笔者认为有些过于诡异，这里给出我自己的二分实现方式（我记得当时是在 B 站学的，但是出自哪个视频忘了）。

1
2
3
4
5
6
7
8

int L = 0, R = n + 1;
while (L + 1 != R) {
    int mid = L + R >> 1;
    if (a[mid] >= x) R = mid;
    else L = mid;
}
if (a[R] == x) cout << R << " ";
else cout << "-1 ";

01 分数规划

用来求一个分式的极值，也就求一组 $w_i=\{0,1\}$，最大化或者最小化：

$$\frac{\sum a_i\times w_i}{\sum b_i\times w_i}$$

我们一般使用二分答案来解决这个问题。以最大值为例：

$$\begin{aligned} &\frac{\sum a_i\times w_i}{\sum b_i\times w_i}>mid\\ \Longrightarrow& \sum a_i\times w_i - mid\times \sum b_i\times w_i > 0\\ \Longrightarrow& \sum w_i(a_i-mid\times b_i)>0 \end{aligned}$$

于是排序即可确定 $w_i$ 的值。有些时候会限制 $\sum b_i\times w_i$ 的最小值之类的，例题，这时使用背包求解即可。

三分法

三分法可以用于求解单峰函数的极值点。对于常规的三分写法不再赘述，但值得注意的是，对于定义域为整数的实际问题，它们的答案可能真的是单峰的，但此时由于其不满足函数的连续性，会存在一大段平的区间，然后三分就炸了（鬼知道极值点在哪，你需要 $O(n)$ 扫过去）。

不要错误的将某些函数视作可以三分，更不要将单峰函数视作凸函数而对导函数二分。单峰的证明是比较困难的，而且有时对于非单峰的问题也比较难找到反例（廊桥分配），要根据实际情况判断。

1
2
3
4
5
6
7

double L = 0, R = 1000;
while (L + eps < R) {
    double Lmid = (L + R) / 2;
    double Rmid = (Lmid + R) / 2;
    if (calcF(Lmid) > calcF(Rmid)) L = Lmid;
    else R = Rmid;
}

wqs 二分

$O(\log n)$

倍增

ST 表

ST 表使用倍增结构来实现，支持在末尾插入一个数。大概长这样：

1
2
3

f[0][n] = a[n]; // The new N
for (int j = 1; 1 << j <= n; ++j)
    f[j][n - (1 << j) + 1] = max(f[j - 1][n - (1 << j) + 1], f[j - 1][n - (1 << j - 1) + 1]);

在开头插入亦同理。

Problemset

** [CF1764G] Doremy’s Perfect DS Class

询问能告诉我们什么？好奇怪啊，不知道。尝试从给定的 $k$ 值开始分析。$k=1$ 没什么意义，然后尝试从特殊的，比如 $k=2,n$ 开始分析。$k=n$ 比较好说，只有 $n$ 可以被记入答案，可以根据此找出 $n$ 的位置。$k=2$ 则可以将数分为两组，在 $n$ 为奇数时只有 $1$ 是单独一组，$n$ 为偶数时只有 $1,n$ 是单独一组。

从别的地方再想一想，都要求 $\log$ 级别的询问，不难想到二分。设 solve(l, r) 代表答案在 $[l,r]$ 的位置中，我们需要确定 $1$ 在 $[l,mid]$ 还是 $[mid+1,r]$ 里。咦，感觉不太对，不是严格的子问题！但是我们只需要寻找答案在哪里，因此只需要分别答案在 $[1,mid]$ 还是 $[mid+1,n]$ 就好了。

选择从 $k=2$ 入手，$x,y$ 分为一组仅当它们除以二下取整后的值相等。我们可以求出两个区间中在自己区间内没有匹配的数的数量，然后这个数量大的，答案就在那里（因为剩下的每有一个都是成对的）。

$n$ 是偶数怎么办呢？我们只需要找到 $n$ 就行，不难发现 $k=n$ 可以很好的完成这个任务。当两个区间的值相等时，说明 $1,n$ 各占一个，我们令 $k=n$，询问其中一个，看 $n$ 是否在其中。找到 $n$ 的位置之后发现之后的递归不会受到影响（如果 $p_n> mid$，我们会递归到 $[l,mid]$，必定有 $p_n>mid'$）。

这个做法可以通过 G2，代码。想过掉 G3，我们需要想方法杀掉那一次多余的询问。

怎么杀？对于 $r-l+1=2$ 的情况，使用两次询问有点浪费，我们看能不能只用一次询问杀掉它。核心思想是，充分利用我们之前问出来的信息。当我们递归到 $[l,r]$ 时，曾令一个 $mid=l-1$，也令了一个 $mid=r$，因此我们知道 $Q(1,l-1,2),Q(1,r,2),Q(l,n,2),Q(r+1,n,2)$ 的答案。现在 $l,r$ 中一个是 $1$，一个是和其他数能匹配上的某个奇怪的东西，吗？注意，另一个可能是 $n$，如果我们还没有确定 $n$ 的位置，那么通过询问 $Q(r,n,n)$ 或 $Q(1,l,n)$ 将其判掉。

现在再看怎么搞 $l,r$ 一个是 $1$，另一个是可匹配数。可匹配数只能配在 $[1,l-1]$ 或 $[r+1,n]$，如果 $Q(1,l-1,2)+1=Q(1,r,2)$，那么说明可匹配数的匹配数是开在 $[1,l-1]$ 的（这个数除以二下去整的值与 $[1,l-1]$ 中的某个数撞了），否则开在 $[r+1,n]$。确定了这一点之后，我们就可以锁定 $1$ 的位置了！以开在 $[1,l-1]$ 为例，如果 $Q(1,l-1,2)=Q(1,l,2)$，说明 $l$ 处开可匹配数，与 $[1,l-1]$ 中的某个数匹配，$1$ 就开在 $r$ 处。

这样在 $r-l+1=2$ 时我们只花费了一次询问，可以通过 G3。代码。