【BZOJ3755】Pty爬山

2016.03.18 14:34 Fri | 32次阅读 | 旧日oi | 固定链接 | 源码

题解

凸包+set

首先处理每个点会以哪个点为目标,这个只要从前往后再从后往前维护一个凸壳就可以了。
然后我们把点排个序,按照4个关键字
1.看到的最高点的高度
2.看到的最高点的位置
2.这个点的高度
3.这个点的位置
高度从从大到小,位置从右到左。
排完序之后我们能发现,决定每个点答案的只和排在它之前的点有关,那么我们就可以依次的加入每个点,同时维护一个set,再加入一个点的时候看它能看到的最高点在左边还是在右边,对应的找到前驱或后继,那么这个点的答案就是走到前驱或后继的步数加上前驱或后继的答案。

my code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
int n;
ll x[N],y[N];
int id[N],mx[N],st[N],top;
int ans[N];
set<int> s;
bool cmp(int a,int b)
{
    if(y[mx[a]]==y[mx[b]]) 
    {
        if(mx[a]==mx[b]) 
        {
            if(y[a]==y[b]) return a>b;
            return y[a]>y[b];
        }
        return mx[a]>mx[b];
    }
    return y[mx[a]]>y[mx[b]];
}
bool check1(int a,int b,int c)
{
    return (x[c]-x[st[b]])*(y[st[b]]-y[st[a]])-(y[c]-y[st[b]])*(x[st[b]]-x[st[a]])<=0;
}
bool check2(int a,int b,int c)
{
    return (x[c]-x[st[b]])*(y[st[b]]-y[st[a]])-(y[c]-y[st[b]])*(x[st[b]]-x[st[a]])>=0;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]);
    for(int i=1;i<=n;i++) 
    {
        while(top>1&&check1(top-1,top,i)) top--;
        if(y[st[top]]>y[i]) mx[i]=st[top];
        else mx[i]=i;
        st[++top]=i;
    }
    top=0;
    for(int i=n;i;i--)
    {
        while(top>1&&check2(top-1,top,i)) top--;
        if(y[st[top]]>y[i]) mx[i]=(y[mx[i]]>y[st[top]]?mx[i]:st[top]);
        else mx[i]=(y[mx[i]]>y[i]?mx[i]:i); 
        st[++top]=i;
    }
    for(int i=1;i<=n;i++) id[i]=i;
    sort(id+1,id+n+1,cmp);
    s.insert(id[1]);
    for(int i=1;i<=n;i++)
    {
        int p=id[i],q=mx[id[i]];
        if(q<p) 
        {
            int x=*(--s.lower_bound(p));
            ans[p]=ans[x]+(p-x);
        }
        else
        {
            int x=*(s.lower_bound(p));
            ans[p]=ans[x]+(x-p);
        }
        s.insert(p);
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}