ASDFZ 3634 -- 小 X 的二叉树

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=200010;

int t,n,k,p[N];
int s1[N][20],s2[N][20];

void maxs() {
	for(int i=1; i<=n; i++)
		s1[i][0]=p[i];
	for(int j=1; j<=18; j++)
		for(int i=1; i<=n; i++) {
			if(i+(1<<j)-1>n)
				break;
			s1[i][j]=max(s1[i][j-1],s1[i+(1<<j-1)][j-1]);
		}
}

void mins() {
	for(int i=1; i<=n; i++)
		s2[i][0]=p[i];
	for(int j=1; j<=18; j++)
		for(int i=1; i<=n; i++) {
			if(i+(1<<j)-1>n)
				break;
			s2[i][j]=min(s2[i][j-1],s2[i+(1<<j-1)][j-1]);
		}
}
 
int gmn(int l,int r) {
	int x=log2(r-l+1);
	return min(s2[l][x],s2[r-(1<<x)+1][x]);
}

int gmx(int l,int r) {
	int x=log2(r-l+1);
	return max(s1[l][x],s1[r-(1<<x)+1][x]);
}

bool check(int l,int r) {
	if(l>=r)
		return true;
	int x=log(r-l+1)/log(2);
	int mn=gmn(l,r),mx=gmx(l,r);
	for(int i=0; i*2<=r-l; i++) {
		if(p[l+i]-k<=mn&&p[l+i]+k>=mx)
			return check(l,l+i-1)&&check(l+i+1,r);
		if(p[r-i]-k<=mn&&p[r-i]+k>=mx)
			return check(r-i+1,r)&&check(l,r-i-1);
	}
	return false;
}

int main () {
	scanf("%d",&t);
	while(t--) {
		scanf("%d%d",&n,&k);
		for(int i=1; i<=n; i++)
			scanf("%d",&p[i]);
		maxs();
		mins();
		if(check(1,n))
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}