线段树什么的最讨厌了

发现如果正着从一颗线段树搜到这一个区间，很难搜。所以考虑从一个区间搜出一颗线段树。

对于一个区间 \([l,r]\)，他的父亲区间只可能是 \([2*l-r-2,r],[2*l-r-1,r],[l,2*r-l],[l,2*r-l-1]\) 四种情况。

发现无论往哪一种方向走，\(\frac{l}{r-l+1}\) 的值都会除以2.那么这么做的复杂度为 \(4^{log_2\frac{l}{r-l+1}}\)。但是我们可以优先 \([2*l-r-2,r],[2*l-r-1,r]\) 搜索，这两种很明显会更加接近答案。加上一些卡常，就可以通过此题。

#include<bits/stdc++.h>
using namespace std;
int t,l,r,lim,ret;
void solve(long long x,long long y)
{if(x>y)return;if(!x){ret=y;return;}
//	printf("%d %d\n",x,y);if(2LL*x-y>=2)solve(2LL*x-y-2,y);	if(2LL*x-y>=1)solve(2LL*x-y-1,y);if(2LL*y-x<ret&&2LL*y-x<=lim)solve(x,2LL*y-x);if(2LL*y-x+1<ret&&2LL*y-x+1<=lim)solve(x,2LL*y-x+1);
}
int main() solve(l,r);printf(ret==2.1e9? "-1\n":"%d\n",ret);}
}

求复杂度证明。