NOIP2012开车旅行（双向链表 + 倍增）

分析

我尼玛，这题目也太长了吧。
emmmm，先考虑70分做法，先 $n^2$n2 处理每个点的最近和次近，每次询问手动模拟。
考虑优化，手动模拟，有点像爬树的过程，可以用倍增优化成 $O\left(mlogn\right)$O(mlogn)。
问题在于，怎么处理出最近和次近呢？
呃呃呃这还是陈老师教我的，用双向链表。
按高度从小到大排序后，从 $1$1 扫到 $n$n ，每次找到 编号为 $i$i 的 左边和右边（左小右大），经过一通比较得到最近和次近后，把 $i$i 从链表中删掉。这样就可以 $O\left(nlogn\right)$O(nlogn) 预处理了。

代码如下

#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 100005
#define LL long long
#define inf 2147483647
using namespace std;
struct node{
    int i, v, l, r;
    bool operator < (const node & A) const{
        return v < A.v;
    }
}d[N];
int stA[N][19], stB[N][19], f[N][19], na[N], nb[N], p[N], l, r, j, a, b;
double ans = inf;
LL z = 1;
int zuo(){
    if(!l) return 0;
    if(!r) return 1;
    return d[j].v - d[l].v <= d[r].v - d[j].v;
}
int pd(int l, int r){
    if(!l) return d[r].i;
    if(!r) return d[l].i;
    if(d[r].v - d[j].v >= d[j].v - d[l].v) return d[l].i;
    return d[r].i;
}
void work(int p, LL x){
    int i;
    for(i = 18; i >= 0; i--){
        if(f[p][i] && z * (a + b + stA[p][i] + stB[p][i]) <= x){
            a += stA[p][i];
            b += stB[p][i];
            p = f[p][i];
        }
    }
    if(na[p] && z * (a + b + stA[p][0]) <= x) a += stA[p][0];
}
int main(){
    int i, n, m, t;
    LL x;
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        d[i].i = i;
        scanf("%d", &d[i].v);
    }
    sort(d + 1, d + i);
    for(i = 1; i <= n; i++) p[d[i].i] = i;
    for(i = 1; i <= n; i++) d[i].l = i - 1, d[i].r = i + 1;
    d[1].l = d[n].r = 0;
    for(i = 1; i <= n; i++){
        j = p[i]; l = d[j].l; r = d[j].r;
        if(zuo()) nb[i] = d[l].i, na[i] = pd(d[l].l, r);
        else nb[i] = d[r].i, na[i] = pd(l, d[r].r);
        if(l) d[l].r = r;
        if(r) d[r].l = l;
    }
    for(i = 1; i <= n; i++){
    	f[i][0] = nb[na[i]];
        stA[i][0] = abs(d[p[i]].v - d[p[na[i]]].v);
        stB[i][0] = abs(d[p[na[i]]].v - d[p[f[i][0]]].v);
    }
    for(i = 1; i <= 18; i++)
        for(j = 1; j <= n; j++){
            f[j][i] = f[f[j][i-1]][i-1];
            stA[j][i] = stA[j][i-1] + stA[f[j][i-1]][i-1];
            stB[j][i] = stB[j][i-1] + stB[f[j][i-1]][i-1];
        }
    scanf("%lld%d", &x, &m);
    for(i = 1; i <= n; i++){
        a = b = 0;
        work(i, x);
        if(b && 1.0 * a / b < ans){
        	ans = 1.0 * a / b;
        	t = i;
		}
    }
    printf("%d\n", t);
    for(i = 1; i <= m; i++){
        a = b = 0;
        scanf("%d%lld", &t, &x);
        work(t, x);
        printf("%d %d\n", a, b);
    }
    return 0;
}