JZOJ 3101【NOIP2012提高组】开车旅行

Description

Analysis

这题比赛时没时间想，直接听了正解。

易看出对于每个点，最近点和次近点要预处理出来。那么，预处理之后怎么办？

对于最暴力的做法，可以一步一步让A和B轮流跳，暴力判断。

等一下，“跳”好像让我们想到了某些东西。

好像可以用倍增，在这题是单点倍增。这里一个点有最近和次近，我们如果要跳，肯定不能分开处理。于是把A走一步之后B也走一完步算作一个轮回。那我们RMQ处理的就是一个轮回。但是还有种情况是B走完之后A还能走，就是n个轮回+A走一步的情况。所以要特判。对于一个轮回的起点和终点，连起来是一棵树吗？显然不可能有环。所以倍增可做。这样单次询问倍增可以做到 O(log2n) 。所以第一问枚举出发点，可以 O(nlog2n) 解决，第二问 O(mlog2n) 。很靠谱。

现在回到预处理。预处理显然不能 n2 。我们观察要求的值的性质，目标点是与它差值的绝对值最小的两个点。所以可以按照高度从小到大快排一遍。这样设当前点在有序数组里的位置是pos，则可能更新到pos的点只有 left[left[pos]],left[pos],right[pos],right[right[pos]] 。其中 left[x] 表示有序数组中排序在x左边的点的编号， right 同理。

但是一个点是不可能往左走的（默认编号从小到大为从左到右排列）。所以每做完一个点，就要删除掉，因为这样才能保证在它右边的点不会被该点更新。这样就不能单用数组，而要用链表维护。

Code

#include<cstdio>
#include<cmath>
#include<cstring>
#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 long long ll;
const int N=100010,M=18,INF=2147483647;
int h[N],c1[N],c2[N],r[N],left[N],right[N];
int n,m,ansa,ansb,pos,f[N][M];
ll d1[N],d2[N],a[N][M],b[N][M];
bool cmp(int x,int y){return h[x]<h[y];}
void pd(int x,int p)
{
    if(!p) return;
    int t=abs(h[p]-h[x]);
    if(t<d1[x] || t==d1[x] && h[p]<h[c1[x]])
    {
        c2[x]=c1[x],c1[x]=p;
        d2[x]=d1[x],d1[x]=t;
    }
    else
    if(t<d2[x] || t==d2[x] && h[p]<h[c2[x]]) c2[x]=p,d2[x]=t;
}
void pre()
{
    sort(r+1,r+n+1,cmp);
    fo(i,1,n) left[r[i]]=r[i-1],right[r[i]]=r[i+1];
    fo(i,0,n) d1[i]=d2[i]=INF;
    fo(i,1,n)
    {
        int l2=left[left[i]],l1=left[i],r1=right[i],r2=right[right[i]];
        pd(i,l2);
        if(l1!=l2) pd(i,l1);
        if(r1!=l1 && r1!=l2) pd(i,r1);
        if(r2!=r1 && r2!=l1 && r2!=l2) pd(i,r2);
        right[left[i]]=right[i],left[right[i]]=left[i];
    }
    fo(i,1,n)
    {
        f[i][0]=c1[c2[i]];
        a[i][0]=d2[i];
        b[i][0]=d1[c2[i]];
    }
    fo(j,1,int(log2(n/2)))
        fo(i,1,n)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            a[i][j]=a[i][j-1]+a[f[i][j-1]][j-1];
            b[i][j]=b[i][j-1]+b[f[i][j-1]][j-1];
        }
}
void DA(int v,int s)
{
    fd(i,int(log2(n/2)),0)
        if(f[v][i] && f[v][i]<=n && s>=a[v][i]+b[v][i])
        {
            ansa+=a[v][i],ansb+=b[v][i];
            s-=a[v][i]+b[v][i];
            v=f[v][i];
        }
    if(c2[v] && c2[v]<=n && s>=d2[v]) ansa+=d2[v];
}
int main()
{
    scanf("%d",&n);
    fo(i,1,n) scanf("%d",&h[i]),r[i]=i;
    pre();
    scanf("%d",&m);
    pos=1;
    double ans=INF;
    fo(i,1,n)
    {
        ansa=ansb=0;
        DA(i,m);
        double t=ansa*1.0/ansb;
        if(t<ans || t==ans && h[i]>h[pos]) pos=i,ans=t;
        else
        if(!ansb && ans==INF && h[i]>h[pos]) pos=i;
    }
    printf("%d\n",pos);
    int _,st;
    scanf("%d",&_);
    while(_--)
    {
        ansa=ansb=0;
        scanf("%d %d",&st,&m);
        DA(st,m);
        printf("%d %d\n",ansa,ansb);
    }
    return 0;
}
           

//学习hjy用下划线做变量