时间复杂度 $O(n\log^2n)$，为啥不加剪枝过不去 1e5 /yiw

ST + 二分答案，check 函数内又套只 $\log$。

怎么会是呢。

疑似本题最劣解

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[100001],ans;
int f[100001][23];
int ask(int l,int r){
	int k=log2(r-l+1);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}
bool chk(ll x){
	ll curr=0;
	for(int i=1;i<=n;++i){
		int l=i,r=n;
		while(l<=r){
			if(a[r]-a[i-1]<=curr)break; // 这句是剪枝
			int mid=(l+r)>>1;
			if(ask(i,mid)<=x){
				curr=max(curr,a[mid]-a[i-1]);
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
	}
//	cout<<x<<" "<<curr<<"\n";
	if(curr<m)return false;
	return true;
}
void work(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		int x;
		cin>>x>>f[i][0];
		a[i]=a[i-1]+x;
	}
	int p=log2(n);
	for(int j=1;j<=p;++j){
		for(int i=1;i+(1<<(j-1))<=n;++i){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	ll l=1,r=1e18;
	while(l<=r){
		long long mid=(l+r)>>1;
		if(chk(mid)){
			r=mid-1;
			ans=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<ans<<"\n";
}
signed main(){
// 	freopen("P4085_5.in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
//	cin>>T;
	while(T--){
		work();
	}
	return 0;
}