笛卡尔树Kattis-Scaffolding
注释已经写在代码里了，注意下建树就行
#include<bits/stdc++.h>
/*先对题意进行分析，每次带m根柱子，进行x轮，每次往左/右/上搭建，问x的最小值？
一开始在想，怎么就会有最小值呢？后来发现题目说不能往下走
我们还是把图看成一棵树
就是说你可以向两个子节点去走，然后花费siz的木条把这个树填满，然后继续选择......
贪心的思想的话，我每一次爬树爬到某个点，材料用完最好（有剩余的话就浪费了，不如去填充其他的？）
也就是说我这一排，能放就放
但是我觉得dp更加稳妥，不知道贪心是不是对的
转移方程呢？
首先应该不是背包问题，因为我求的是轮数，没有“占用空间”这一回事
而且我用贪心，尽力填充下层，所以不存在背包问题
那就是简单的dp了
ans=f[i],表示建设到以根i为子树需要的轮
但我肯定要知道还剩了多上根柱子建造后面的啊
g[i]带了f[i]轮竹子，当前区间高度达到h[i]后剩多少竹子来搭更父亲节点部分的竹子。
*/
#define int long long
using namespace std;
int n,m,rt;
int head,tail;
int a[100100],sons[100010][2],q[100010];
int l[100010],r[100010];
long long f[100010],g[100010];
inline void dfs(int x,int fa){
l[x]=r[x]=x;
if(sons[x][0]){
dfs(sons[x][0],x);
f[x]+=f[sons[x][0]];
g[x]+=g[sons[x][0]];
l[x]=l[sons[x][0]];
}
if(sons[x][1]){
dfs(sons[x][1],x);
f[x]+=f[sons[x][1]];
g[x]+=g[sons[x][1]];
r[x]=r[sons[x][1]];
}
long long used=1ll*(r[x]-l[x]+1)*(a[x]-a[fa])-g[x];
if(used<0){//剩余柱子
g[x]=-used;
}
else{//往上攀升
long long d=used/m;
if(used%m!=0){
d++;
}//注意这里是要用完的，轮数要++
f[x]+=d;
g[x]=d*m-used;
}
}
inline int read(){
int x=0,f=1;
char sons=getchar();
while(sons<'0'||sons>'9')
{
if(sons=='-')
f=-1;
sons=getchar();
}
while(sons>='0' && sons<='9')
x=x*10+sons-'0',sons=getchar();
return x*f;
}
signed main() {
n=read();
m=read();
rt=1,head=1,tail=0;
for(int i=1;i<=n;i++){
a[i]=read();
}
memset(sons,0,sizeof(sons));//不用也可以
for(int i=1;i<=n;i++) {
int res=-1;
while(head<=tail&&a[i]<=a[q[tail]]){
res=q[tail--];
}
if(res!=-1) {
if(rt==res)rt=i;
sons[i][0]=res;
}
if(head<=tail)sons[q[tail]][1]=i;
q[++tail]=i;
}//正常建树
l[rt]=1;
r[rt]=n;
dfs(rt,0);
// for(int i=1;i<=n;i++){
//cout<<l[i]<<" "<<r[i]<<endl;
// }
cout<<f[rt];
}