记录编号	566362	评测结果	AAAAAAAAAA
题目名称	[NOIP 2018]铺设道路	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2021-11-06 13:38:22	内存使用	4.20 MiB

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
ull ans;
int nc;
int n[20][100001][2]; 
int ej(int x)
{
	int re=1;
	while(x>>re) re++;
	return --re;
}
void cz(int l,int r,int dn)
{
	if(l==r)
	{
		ans+=(n[0][l][0]-dn);
		return;
	}
	int th=ej(r-l+1);
	int thp=(1<<th);
	int md;
	if(n[th][l][0]<=n[th][r-thp+1][0])
	{
		md=n[th][l][1];
		ans+=(n[th][l][0]-dn);
		dn=n[th][l][0];
	}
	else
	{
		md=n[th][r-thp+1][1];
		ans+=(n[th][r-thp+1][0]-dn);
		dn=n[th][r-thp+1][0];
	}
	if(md!=l) cz(l,md-1,dn);
	if(md!=r) cz(md+1,r,dn);
	return;
}
int main()
{
    freopen("2018road.in","r",stdin);
	freopen("2018road.out","w",stdout);
    cin>>nc;
    for(int i=1;i<=nc;i++)
    {
    	scanf("%d",&n[0][i][0]);
    	n[0][i][1]=i;
    }
    for(int i=1;(1<<i)<=nc;i++)
    {
    	for(int st=1;st+(1<<i)-1<=nc;st++)
    	{
    		if(n[i-1][st][0]<=n[i-1][st+(1<<(i-1))][0])
    		{
    			n[i][st][0]=n[i-1][st][0];
    			n[i][st][1]=n[i-1][st][1];
    		}
    		else
    		{
    			n[i][st][0]=n[i-1][st+(1<<(i-1))][0];
    			n[i][st][1]=n[i-1][st+(1<<(i-1))][1];
    		}
    	}
    }
    cz(1,nc,0);
    cout<<ans<<endl;
    return 0;
}