F. ATM and Students
金典对于一个区间我们不能让他+的过程中出现负数
我们ST表处理前缀和区间最小数
然后再二分长度 暴力枚举左右端点
时间复杂度是O(nlogn)
哦 还要注意的是
我们二分一个数时 如果会有不合法的解
我们应该扩大一下左右边界 然后再加判断
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int f[N][31],n,a[N],s[N],x,ans_l,ans_r;
void init(){
for(int len=0;len<30;len++){
for(int i=1;i+(1<<len)-1<=n;i++){
if(!len)f[i][len]=s[i];
else f[i][len]=min(f[i][len-1],f[i+(1<<(len-1))][len-1]);
} //i+1<<len-1的话是包括了i 不用加1
}
}
int query(int l,int r){
int len=r-l+1;
int k=log(len)/log(2);
return min(f[l][k],f[r-(1<<k)+1][k]); //而r-1<<k是没有包含到r所以要+1
}
bool check(int len){
for(int i=1,j=i+len-1;j<=n;i++,j++){
if(query(i,j)-s[i-1]+x>=0){
ans_l=i,ans_r=j;
return true;
}
}
return false;
}
void solve() {
cin>>n>>x;
for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];
init();
int l=1,r=n;
ans_l=ans_r=0;
while(l<r){
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
if(ans_r)cout<<ans_l<<' '<<ans_r<<endl;
else cout<<-1<<endl;
}
signed main(){
fast
int t;t=1;cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}
标签:return,756,int,Codeforces,long,mid,ans,const,Div
From: https://www.cnblogs.com/ycllz/p/16825646.html