小白月赛74g题--wqs二分

花了一天学会的，感觉是个很帅的东西（。。。

需要会的一点东西,单调栈优化dp,wqs二分。

观察将梯子的数量设为x，对应的最小疲劳值为y，这是一个凸函数；
感性的理解下，因为答案为最优不重区间所以在不超过这些区间的数量之前是越多越好的，超过了就必须将区间断开来获得更多的区间，同时答案会变劣。

然后套用wqs部分（网上教的挺好的，逃~）
感觉主要是不带限制个数的最值求解复杂度能接受，然后由凸函数性质做带权二分（

先求一下斜率为0的时候需要的数量，如果那个数量  <= m,那么答案就是斜率为0时的y值。
否则由函数图像可以知道答案为x = m的y值。

然后还需要如何o（n）的求最小的x与b，注意求的时候每用一次桥就减一次k
问题变成了没有m的限制的版本
考虑单调栈dp，不断的将栈顶位置与当前位置转移一次，如果栈顶的高度小就将栈顶pop再重复一次。
最后再将当前位置塞进去。
显然栈中小于当前位置与第一个大于等于的都可以与当前位置转移。

复杂度O(nlogw),w为斜率的值域(建议二分填L,R的时候填大一点) 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
#define rep(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
//#define db double
ll n,m,dp[N],h[N],cn[N];
stack<ll>q1;
struct node{
	ll b,x;
};

node ck(ll t){//返回b与x
	while(!q1.empty())q1.pop();
	q1.push(1);
	rep(i,2,n){
		dp[i] = dp[i-1] + abs(h[i]-h[i-1]),cn[i] = cn[i-1];
		while(!q1.empty()){
			ll k1 = dp[q1.top()]+abs(h[q1.top()]-h[i])-t;
			
			if(k1 == dp[i])cn[i] = min(cn[i],cn[q1.top()]+1);//不会证为什么要取最小的（
			if(k1 < dp[i])dp[i] = k1,cn[i] = cn[q1.top()]+1;
			
			if(h[q1.top()] >= h[i])break;
			q1.pop();
		}
		q1.push(i);
	}
	return {dp[n],cn[n]}; 
}

void erfen(ll l,ll r,ll x){//wqs二分
	while(l < r){
		ll mid = l+(r-l+1)/2-1;
		if(ck(mid).x >= x)r = mid;
		else l = mid+1;
	}
	cout<<r*x + ck(r).b<<'\n';//此时r为k
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	rep(i,1,n)cin>>h[i];
	
	if(ck(0).x <= m)cout<<ck(0).b<<'\n';//k为0
	else erfen(-1e16,1e16,m);
	return 0;
}