LINK：爬山
很早以前看的題目 發現自己想的完全不對 這道題還是比較有價值的。
先不考慮走的路線問題 考慮某個點能看到的最高的山。
分左邊和右邊來考慮 考慮左邊 利用單調棧存長度單調遞減的山 不能直接取最高的 因為最高的山可能被遮住了。
然後分析到底哪座山可以取 設目前點為i 對于一個點k來說 如果存在j<k 且 j,k,i連線是一個下凸包那麼k就沒用了。
容易發現如果把這些下凸包删掉 就是一個上凸包了 取凸包上和i相鄰的點即可。
至此 得到一個通解左邊形成的凸包離i最近的點 右邊同理。
接下來考慮 如何求答案 暴力模拟可能複雜度很高 因為從一座山走到另一座山的途中路線可能會被修改。
容易從中發現 目前點會到達某個點 某個點會繼續走下去 此時高度比原來大。
顯然 這種順序不存在環 是以隻要找到這樣的順序就可以快速得到答案了。
進一步的可以發現 每個點都會到達最高的那個點 是以這些關系形成了一棵樹。
const int MAXN=500010;
int n,top;
struct wy
{
int x,y;
}t[MAXN];
ll f[MAXN];int vis[MAXN];
int mx[MAXN],s[MAXN],fa[MAXN];
inline int pd(int i,int j,int k)
{
return (ll)(y(i)-y(j))*(x(j)-x(k))<(ll)(y(j)-y(k))*(x(i)-x(j));
}
inline ll dfs(int x)
{
if(vis[x])return f[x];
vis[x]=1;
if(!fa[x])return f[x];
return f[x]=dfs(fa[x])+abs(x-fa[x]);
}
int main()
{
freopen("1.in","r",stdin);
get(n);y(0)=-1;
rep(1,n,i)get(x(i)),get(y(i));
rep(1,n,i)
{
while(top>1&&pd(s[top-1],s[top],i))--top;//形成下凸包.
mx[i]=s[top];s[++top]=i;
}
top=0;
fep(n,1,i)
{
while(top>1&&pd(i,s[top],s[top-1]))--top;
mx[i]=y(s[top])>=y(mx[i])?s[top]:mx[i];s[++top]=i;
}
fep(n,1,i)if(y(mx[i])<=y(i)){mx[i]=i;break;}
top=0;
rep(1,n,i)
{
while(top&&(y(mx[i])>y(mx[s[top]])||(y(mx[i])==y(mx[s[top]])&&x(mx[i])>x(mx[s[top]]))))--top;
if(mx[i]<i)fa[i]=s[top];s[++top]=i;
}
top=0;
fep(n,1,i)
{
while(top&&(y(mx[i])>y(mx[s[top]])||(y(mx[i])==y(mx[s[top]])&&x(mx[i])>x(mx[s[top]]))))--top;
if(mx[i]>i)fa[i]=s[top];s[++top]=i;
}
rep(1,n,i)dfs(i),putl(f[i]);
return 0;
}