题解：P16434 [APIO 2026 中国赛区] 蛋糕
-
Subtask1：搞个什么
1,2,3\dots w 或w 个1 都行。 -
Subtask2：搞两个
1 凑出来2 ，然后小于等于大于分别对应三种情况。 -
Subtask3：
10^9,30 ，搞个什么2^0\sim 2^{29} ，然后先倒着问一遍确定d 在排完序中的哪个位置（可以通过\sum_{i=0}^{j-1}2^i 和“假想中“2^j 的大小来确定）。然后二分。
这样询问次数是30+O(1) 的，我的写法需要特判一下2^k-1 。 -
Subtask4：注意到每次询问会有三种结果，而
N+200=2200 恰好大于2187 ，而\lfloor\log _3W\rfloor=7 。假设当前确定了d 在[l, r) 中，我取三等分点p<q ，然后l+r=p+q 的。询问几乎就是这两个东西。 -
然后可以取 bake_cakes 为
1\sim 2187 。这样注意到我d 落在[l, p),[p, q),[q,r) 的时候，S_2+1 和S_1 正好是小于，等于，大于。充分利用了三种情况。所以总的询问次数就是三为底对数。