【JZOJ 3401】Pty爬山

Description

坐标系裡有N個點，保證他們的x坐标遞增，它們互相連接配接形成一些連續的線段。每個點會向自己的位置能看到的最高點（能看到指視線不經過其它線段）沿着線段移動。若移動過程中到達的點能看到的最高點比原先的最高點高，則向新的最高點移動……若該點就是最高點則停止移動。求從每個點出發移動的步數。

Analysis

題目沒有說明，但是資料是三點共線是可以被看見的（這證明了地球不是圓的2333）。

這道題我花了整場比賽去搞，結果比賽時隻有10分QAQ.

首先預處理出每個點能夠看到的最高點。正反各搜一遍，比較一下斜率就好了。 O(n) 解決。

然後一個直覺的想法就是模拟走路的過程。但是這樣最壞情況可以達到 O(n3) ，于是爆炸。

顯然地，無需如此暴力。

我們可以用一棵線段樹，記錄每個點能看到的最高點的高度。這樣走的時候直接線段樹查詢，複雜度變成 O(n2log2n) ，這樣就能拿到60分了。

實際上，我們可以發現，這道題的圖的關系還是比較顯著的。我們隻需讓每個點能看到的最高點向該點連邊。然後從全圖最高點開始bfs一遍記錄邊權更新每個點的答案就好了。 O(nlog2n) ，于是乎就能通過所有資料了。

Code

#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
typedef double db;
const int N=,M=N*2;
int n,pos,b[N],b1[N],b2[N],mx[N*4];
int tot,to[M],wei[M],next[M],last[N],dis[N];
queue<int> q;
struct point
{
    int x,y;
}a[N];
db slope(point a,point b){return (a.y-b.y)*1./(a.x-b.x);}
void link(int u,int v,int w)
{
    to[++tot]=v,wei[tot]=w,next[tot]=last[u],last[u]=tot;
}
void pre()
{
    scanf("%d",&n);
    fo(i,,n) scanf("%d %d",&a[i].x,&a[i].y);
    fd(i,n-,) b1[i]=i+;
    b1[n]=n;
    fd(i,n-,)
        for(;slope(a[i],a[b1[b1[i]]])>=slope(a[i],a[b1[i]]);b1[i]=b1[b1[i]])
            if(b1[i]==n) break;
    fo(i,,n) b2[i]=i-;
    b2[]=;
    fo(i,,n)
        for(;slope(a[i],a[b2[b2[i]]])<=slope(a[i],a[b2[i]]);b2[i]=b2[b2[i]])
            if(b2[i]==) break;
    fo(i,,n)
    {
        b[i]=i;
        if(a[b1[i]].y>=a[b[i]].y) b[i]=b1[i];
        if(a[b2[i]].y>a[b[i]].y) b[i]=b2[i];
    }
}
void build(int v,int l,int r)
{
    if(l==r)
    {
        mx[v]=a[b[l]].y;
        return;
    }
    int mid=(l+r)>>;
    build(v*2,l,mid);
    build(v*2+,mid+,r);
    mx[v]=max(mx[v*2],mx[v*2+]);
}
void findl(int v,int l,int r,int z)
{
    if(mx[v]<z) return;
    if(l==r)
    {
        pos=min(pos,l);
        return;
    }
    int mid=(l+r)>>;
    if(mx[v*2]>=z) findl(v*2,l,mid,z);
    else
    if(mx[v*2+]>=z) findl(v*2+,mid+,r,z);
}
void findr(int v,int l,int r,int z)
{
    if(mx[v]<z) return;
    if(l==r)
    {
        pos=max(pos,r);
        return;
    }
    int mid=(l+r)>>;
    if(mx[v*2+]>=z) findr(v*2+,mid+,r,z);
    else
    if(mx[v*2]>=z) findr(v*2,l,mid,z);
}
void find(int v,int l,int r,int x,int y,int z,bool p)
{
    if(l==x && r==y)
    {
        if(p) findr(v,x,y,z);
        else findl(v,x,y,z);
        return;
    }
    int mid=(l+r)>>;
    if(y<=mid) find(v*2,l,mid,x,y,z,p);
    else
    if(x>mid) find(v*2+,mid+,r,x,y,z,p);
    else find(v*2,l,mid,x,mid,z,p),
    find(v*2+,mid+,r,mid+,y,z,p);
}
int val(int x,int y)
{
    pos=y;
    if(x<y)
    {
        x++;
        find(,,n,x,y,a[y].y+,);
        return pos;
    }
    x--;
    find(,,n,y,x,a[y].y,);
    return pos;
}
void bfs(int S)
{
    q.push(S);
    dis[S]=;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=last[u];i;i=next[i])
        {
            int v=to[i];
            dis[v]=dis[u]+wei[i];
            q.push(v);
        }
    }
}
int main()
{
    pre();
    build(,,n);
    int root=;
    fo(i,,n)
    {
        if(i==b[i]) {root=i;continue;}
        int j=val(i,b[i]);
        link(j,i,abs(i-j));
    }
    bfs(root);
    fo(i,,n) printf("%d\n",dis[i]);
    return ;
}