A
你有 \(m\) 个相同的球，球有性能 \(c\)，你可以测试 \(x\)，若 \(x\ge c\)，那么球会碎掉，若 \(x< c\)，那么球不碎。
性能的范围 \(n\le 1e5\)。求最多要测试多少次。
首先答案有一个上限是 \(\log n\)。所以令 \(m\to \min(m,\log n)\)
所以我们记状态可以记 \(dp_{l,r,k}\) 表示当前确定性能区间是 \([l,r]\)，还剩 \(k\) 个球，至少测试几次。
然而这样状态数太大，发现每个区间是等价的，那我们记状态是 \(dp_{i,k}\) 表示确定性能区间长度为 \(i\)，还剩 \(k\) 个球。
考虑转移，\(dp_{i,k}=\min(\max(dp_{j,k-1},dp_{i-j,k}))\).
发现 \(\max(dp_{j,k-1},dp_{i-j,k})\) 是单峰的，所以可以三分。
其实有更优的，注意到 \(dp_{j,k-1}-dp_{i-j,k}\) 的值越接近 \(0\)，那么 \(\max(dp_{j,k-1},dp_{i-j,k})\) 越小。
那么直接二分即可。
B
有 \(n\) 个点，每个点 \(i\) 到 \([l_i,r_i]\) 区间里的点有连有向边。
你需要在这张图上玩有向图游戏，从 \(1\sim n\) 的每个点都开始一遍。
求每个点的 \(SG\) 函数。
我们从 \(1\sim n\) 去遍历，\(SG(i)=mex(SG(l_i),...,SG(r_i))\).
发现就是区间求 \(mex\) 问题。这个经典的问题可以用主席树去实现。
我们第 \(i\) 个版本维护的是 \(1\sim i\) 里面，所有 \(SG\) 函数的值最后一次出现的位置。
对于查询 \([l,r]\)，在第 \(r\) 个版本，二分出 \(mex\) 值。
只需要维护区间最小值，二分出第一个位置小于 \(l\) 的权值即可。