BD202429 毕业照(binary lift facilitate the calculation) · znzryb
## 思路讲解
前两问用二分，贪心解决。
最后一问需要使用双指针+倍增法。
## AC代码
[https://www.matiji.net/exam/oj/submit-detail/13507760/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD](https://www.matiji.net/exam/oj/submit-detail/13507760/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD)
::: 源代码
```cpp
// https://www.matiji.net/exam/brushquestion/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,lT,H[MAXN],D;
/*
*/
inline void init(){
}
struct cmpda{
bool operator()(ll a,ll b){
return H[a]<H[b];
}
};
struct cmpxiao{
bool operator()(ll a,ll b){
return H[a]>H[b];
}
};
inline void solve(){
cin>>N>>K>>D;
init();
FOR(i,1,N){
cin>>H[i];
}
ll lans2=0;
auto check1=[&](ll mid)->bool{
ll bp=1,res=0;
while(bp<=N){
ll i=bp;
ll mn=H[i],mx=H[i];
bool isB=false;
FOR(j,i,N){
// #ifdef LOCAL
// debug(H[j]-mn);
// debug(H[j]-mx);
// #endif
if(abs(H[j]-mn)<=mid && abs(H[j]-mx)<=mid){
// #ifdef LOCAL
// cerr<<"OKAY\n";
// #endif
mn=min(H[j],mn);
mx=max(H[j],mx);
}else{
bp=j;
++res;
isB=true;
break;
}
}
if(!isB){
++res;
break;
}
}
// #ifdef LOCAL
// debug(mid);
// debug(res);
// #endif
lans2=res;
if(res>K){
return false;
}
return true;
};
ll l=0,r=mod;
while(l<r){
ll mid=l+r>>1;
if(check1(mid)){
r=mid;
}else{
l=mid+1;
}
}
cout<<l<<"\n";
check1(D);
cout<<lans2<<"\n";
vector<ll> nextPos(N+5,0);
auto cal=[&]()->void{
ll bp=1,res=0;
priority_queue<ll,vector<ll>,cmpda> da;
priority_queue<ll,vector<ll>,cmpxiao> xiao;
FOR(i,1,N){
bool isB=false;
FOR(j,bp,N){
while(da.empty()==false && (da.top()<i || da.top()>j) ){
da.pop();
}
while(xiao.empty()==false && (xiao.top()<i || xiao.top()>j)){
xiao.pop();
}
ll mx=da.empty()?H[j]:H[da.top()],mn=xiao.empty()?H[j]:H[xiao.top()];
if(abs(H[j]-mx)<=D && abs(H[j]-mn)<=D){
xiao.push(j);
da.push(j);
}else{
bp=j;
nextPos[i]=j-1;
// #ifdef LOCAL
// debug(i);
// #endif
isB=true;
break;
}
}
if(!isB){
nextPos[i]=N;
bp=N+1;
}
}
};
cal();
ll mx_k=ceil(log2(K+1))+1;
bitset<32> bik(K);
vector<vector<ll> > jump(N+5,vector<ll>(mx_k+2,0));
ROF(i,N+1,1){
jump[i][0]=i<=N?nextPos[i]+1:N+1;
// if(i==N){
// FOR(j,0,mx_k) jump[i][j]=N+1;
// continue;
// }
FOR(j,1,mx_k){
jump[i][j]=jump[jump[i][j-1]][j-1];
// if(jump[i][j]==0) jump[i][j]=N+1;
}
}
// FOR(t,0,mx_k){
// FOR(i,1,N){
// if(t==0) {jump[i][t]=nextPos[i]+1;continue;}
// jump[i][t]=jump[jump[i][t-1]][t-1];
// }
// }
ll ans=0;
// #ifdef LOCAL
// FOR(i,1,N+1){
// FOR(j,0,mx_k){
// cerr<<jump[i][j]<<" ";
// }
// cerr<<"\n";
// }
// FOR(i,1,N){
// cerr<<nextPos[i]<<" ";
// }
// cerr<<"\n";
// #endif
FOR(i,1,N){
ll lans=0,idx=i;
FOR(j,0,mx_k){
if(bik[j]){
idx=jump[idx][j];
}
// #ifdef LOCAL
// debug(i);debug(idx);
// #endif
}
lans=idx-i;
ans=max(ans,lans);
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--){
// solve();
// }
solve();
return 0;
}
/*
AC
https://www.matiji.net/exam/oj/submit-detail/13507760/29/4498/F16DA07A4D99E21DFFEF46BD18FF68AD
*/
```
:::
## 心路历程（WA，TLE，MLE……）
调了比较久，最后终于是调出来了。最重要的就是这个倍增的板子，需要从N+1开始遍历。
```cpp
vector<vector<ll> > jump(N+5,vector<ll>(mx_k+2,0));
ROF(i,N+1,1){
jump[i][0]=i<=N?nextPos[i]+1:N+1;
FOR(j,1,mx_k){
jump[i][j]=jump[jump[i][j-1]][j-1];
}
}
```