Scaffolding 2016ICPC香港現場賽 笛卡爾樹+貪心

https://open.kattis.com/problems/scaffolding

學習自https://blog.csdn.net/tianyizhicheng/article/details/107960981

感覺這場題目品質挺高的，中間幾題都可做，不過對超高水準隊伍應該偏容易了一點，這題題目意思有些問題，不然現場應該是有隊過的，感覺最難的是I題(流下了不會構造的淚水)，有個關鍵的點時你撘了一個short竹子以後，必須爬到那上面，補題的時候研究了好久的樣例2都想不明白，看了一眼題解以後就會做了。

因為高的位置肯定要最後放，因為你向上爬了以後就下不來了，那麼肯定就是從高的位置往低的位置貪心，為了使得高的地方能建到，我們必須先把低的地方搭好。直接建小根堆的笛卡爾樹，每次求把目前節點所代表的區間的高度變成父節點所統治的區間的高度，需要f[i]輪帶m竹子，且由于這f[i]輪帶竹子還可以幫忙解決一些比這高度低的位置的竹子，是以還要記錄一個g[i]為帶了f[i]輪竹子吧目前區間高度變成h[i]以後還剩多少竹子可以用來搭更低部分的竹子。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxl=1e5+10;

int n,m,rt;ll ans;
ll a[maxl];
ll f[maxl],g[maxl];
struct node
{
	ll k,val,fa,ls,rs,l,r;
}tr[maxl];

inline int build()
{
	int k;
	for(int i=1;i<=n;i++)
	{
		k=i-1;
		while(tr[k].val>tr[i].val)
			k=tr[k].fa;
		tr[i].fa=k;
		tr[i].ls=tr[k].rs;
		tr[tr[k].rs].fa=i;
		tr[k].rs=i;
	}
	return tr[0].rs;
}

inline void prework()
{
	scanf("%d%d",&n,&m);
	tr[0]={0,0,0,0,0,1,n};
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		tr[i]=node{i,a[i],0,0,0,0,0};
	}
	rt=build();
}

inline void dfs(int k)
{
	tr[k].l=tr[k].r=tr[k].k;
	if(tr[k].ls)
	{
		dfs(tr[k].ls);
		f[k]+=f[tr[k].ls];
		g[k]+=g[tr[k].ls];
		tr[k].l=tr[tr[k].ls].l;
	}
	if(tr[k].rs)
	{
		dfs(tr[k].rs);
		f[k]+=f[tr[k].rs];
		g[k]+=g[tr[k].rs];
		tr[k].r=tr[tr[k].rs].r;
	}
	if(k==0)
		return;
	ll tmp=1ll*(tr[k].r-tr[k].l+1)*(tr[k].val-tr[tr[k].fa].val)-g[k];
	if(tmp<0)
		g[k]=-tmp;
	else
	{
		ll d=tmp/m;
		if(tmp%m!=0) d++;
		f[k]+=d;g[k]=d*m-tmp;
	}
}

inline void mainwork()
{
	dfs(0);
	ans=f[0];
} 

inline void print()
{
	printf("%lld",ans);
}

int main()
{
	prework();
	mainwork();
	print();
	return 0;
}