【JZOJ4208】线段树什么的最讨厌了【搜索】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/4208

这是一个线段树建树的代码。

void buildtree(int k1,int l,int r){
	if (l==r) return;
	int mid=(l+r)/2;
	buildtree(k1*2,l,mid); buildtree(k1*2+1,mid+1,r);
}

若一个根节点为$[0,n)(nin0sim lim)$的线段树包含了区间$l,r$，求$n$的最小值、

---

思路：

对于一个区间$l,r$，长度为$len$，它的父节点只可能有以下四个：

• $[l,r+len-1)$
• $[l,r+len)$
• $[l-len,r)$
• $[l-len-1,r)$

那么就从$l,r$往上搜索，取最优答案即可。
然后就能愉快的拿到$30$分。
这样的时间复杂度太高了。考虑剪枝。
我们发现，如果$l$不是$0$的话，那么就可以扩张到区间$[l,r+len-1)$或$[l,r+len)$。那么此时$l$还是不等于$0$，所以只有往左扩张才可能使$l$为$0$。但是扩张一次就相当于长度乘$2$，也就是往左扩张$2len$。但是如果$l<2len$，那么就无法扩张，所以也就无法扩张成$[l,r+len-1)$或$[l,r+len)$。
这样就可以过了。

---

代码：

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

ll L,R,lim,ans,Read;
int T;
char ch;

ll read()
{
	Read=0;
	ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9')
		Read=(Read<<3)+(Read<<1)+ch-48,ch=getchar();
	return Read;
}

ll write(ll x)
{
	if (x>9) write(x/10);
	putchar(x%10+48);
}

void dfs(ll l,ll r)
{
	if (l<0||r>lim) return;  //超过范围
	if (!l)  //满足要求
	{
		ans=min(ans,r);
		return;
	}
	ll len=r-l+1;
	if (l>=len*2-1) dfs(l,r+len-1);
	if (l>=len*2) dfs(l,r+len);  //剪枝
	dfs(l-len,r);
	dfs(l-len-1,r); 
}

int main()
{
	T=read();
	while (T--)
	{
		L=read(),R=read(),lim=read();
		if (L==R) write(L);
		else
		{
			ans=lim+1;
			dfs(L,R);
			if (ans<lim) write(ans);
				else putchar('-'),putchar('1');
		}
		putchar(10);
	}
	return 0;
}