CF19D(树套树)

一道非常有意思的树套树。

一眼一个空间\(n\log n\)时间\(n \log^{2} n\)的树套树，发现过不了。考虑优化。我们发现在中间线段树的地方可以不用平衡树存下来，只记最大值即可。然后我们对于每个横坐标开一颗fhq,然后分出\(\log n\)段区间，这些区间的最大值大于给定点的纵坐标。然后用二分找到最左的点，然后在这里找到最下的点即可。

void get(int l,int r,int k,int p){
	if(l==r){
		cout<<a[l]<<" "<<getnxt(l,k)<<"\n";
		flag=1;
		return;
	}
	int mid=(l+r)>>1;
	if(d[p<<1]>k) get(l,mid,k,p<<1);
	else if(d[p<<1|1]>k) get(mid+1,r,k,p<<1|1);
}
void getsum(int l,int r,int p,int s,int t,int k){
	if(flag==1) return;
	if(l>=s&&r<=t){
		//cout<<l<<"-"<<r<<"\n";
		if(d[p]>k) get(l,r,k,p);
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid) getsum(l,mid,p<<1,s,t,k);
	if(t>mid) getsum(mid+1,r,p<<1|1,s,t,k);
}