众所周知有一种很实用的算法叫做二分答案。
二分答案可以解决一些答案具有单调性的问题。
比如说：洛谷 P2678 跳石头，这是再基本不过的二分答案了吧？
答案满足单调性意为，如果让你找的答案为满足某种条件的最小值x，那么大于x的所有值也都合法，小于x的所有值都不合法。
或者是，如果让你找的答案为满足某种条件的最大值x，那么小于x的所有值也都合法，大于x的所有值都不合法。
合法或不合法的判定在于check函数的返回值。
这个二分答案的算法一般是这样实现的：（以跳石头为例）
int ans; int ll=0; int rr=maxl; while(ll<=rr) { int mid=(ll+rr)/2; if(check(mid)) { ll=mid+1; ans=mid; }else { rr=mid-1; } }
最后求出来的ans就是答案。
可以看出，最短跳跃距离很小的时候都能被满足，所以题目要求我们求一个最大值。
而且满足单调性：比某个值大的距离都不能被满足，小于等于某个值的距离都可以被满足。
这就是单调性。
因为满足单调性，所以用二分答案就行。
但是经过长时间的应用我发现二分答案有一些小缺点：l、r的边界判断（即while循环的退出条件）很烧脑。
又联想到倍增LCA的算法实际上也是一个类似二分答案的过程。
比LCA浅的节点都是公共祖先，比LCA深的节点都不是公共祖先，我们要在这里找一个最近（也就是最深）公共祖先（LCA）。
但是这里我们利用数的二进制表示来倍增，而并没有二分答案。
所以我想到了倍增答案的算法，类似倍增LCA。
还是以跳石头为例：
int ans=0; for(int i=30;i>=0;i--) { if(check(ans|(1<<i)))ans|=(1<<i); }
这样之后，ans的值就是答案。
可以看出代码与倍增LCA很相似。
正确性也是毋庸置疑。
只要i这一位加上去还合法，那就加上去。
最后肯定得到一个合法且最大的值，也就是合法的最大值。
那么如果大的值都合法，让我们求一个合法的最小值呢？
合法的最小值不就是不合法的最大值+1嘛。
这样我们求出不合法的最大值就行了。
int ans=0; for(int i=30;i>=0;i--) { if(!check(ans|(1<<i)))ans|=(1<<i); } ans=ans+1;
倍增答案大法好！
如果各位大佬发现了什么bug请在底下评论哦~
谢谢！