线段树什么的最讨厌了

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

对于一个区间 \([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);
	}
}

求复杂度证明。