Description：
就是两个人开车，只能向东开。向东有n个城市，城市之间的距离为他们的高度差。A，B轮流开车，A喜欢到次近的城市，B喜欢到最近的城市。如果车子开到底了或者车子开的路程已经超过了限制X就停。
问你从一个点出发，最后A行驶的里程数和B行驶的里程数。
倍增的妙用，这道题改变了我对NOIP的看法。让我对着书看了好久才看懂
不过70分还是好拿的，就是预处理然后对每个询问$O(n)$ 模拟一遍。复杂度$O(nlog_{2}n+nm)$
怎么预处理？就是找到一个城市$i$后离他最近的城市和次近的城市，分别为$gb[i]$，$ga[i]$，用平衡树(set)或者链表或者权值线段树实现
满分在70分的基础上，倍增预处理，然后$O(log_{2}n)$回答每个询问
对于第一个询问，枚举起点即可。
接下来， $dp[i][j][k]$表示$k$在$j$点出发，共开$2^i$天的车到达的城市，1表示A，2表示B。
$sta[i][j][k]$表示$k$在$j$点出发，共开$2^i$天的车A所行驶的路程，$stb[i][j][k]$表示$k$在$j$点出发，共开$2^i$天的车B所行驶的路程。
边界和初值：$dp[0][j][0]=ga[j]$，$dp[0][j][1]=gb[j]$，$sta[0][j][0]=dist(j,ga[j])$，$stb[0][j][1]=dist(j,gb[j])$ 其他都为0
转移看代码，特别注意的是因为$i=1$时，两人是换着开的，所以转移的时候k要去个反。而$i>1$的话，$2^i$天和$2^{i-1}$时开车的人是相同的故不用取反
其他对着状态就能理解了把，就不写注释了。
/*代码修改自李煜东霸霸，变量名是按照书上说法开的*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + ;
#define ll long long
ll sta[][N][], stb[][N][], ansA, ansB, la, lb;
int dp[][N][], n, m, ga[N], gb[N], h[N], i, t, ans;
struct node{ int x, y;} ;
set<node> s;
set<node>::iterator it,lt,rt;
int dist(int x, int y){ return abs(h[x] - h[y]); }
bool cmp(int x, int y){ return dist(x, i) == dist(y, i) ? h[x] < h[y] : dist(x, i) < dist(y, i); }
bool operator < (node a, node b){ return a.y < b.y; }
void solve(int s, int X){
la = lb = ; int k = ;
for(int j = t; j >= ; j--)
if(dp[j][s][k] && sta[j][s][k] + stb[j][s][k] <= X){
X -= (sta[j][s][k] + stb[j][s][k]);
la += sta[j][s][k], lb += stb[j][s][k];
if(j == ) k ^= ;
s = dp[j][s][k];
}
}
int main(){
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &h[i]);
for(i = n; i >= ; i--){
node tmp; tmp.x = i, tmp.y = h[i];
int temp[];
s.insert(tmp); it = s.find(tmp);
lt = it, rt = it, m = ;
if(lt != s.begin()) lt--, temp[++m] = lt -> x;
if(lt != s.begin()) lt--, temp[++m] = lt -> x;
if(rt++, rt != s.end()){
temp[++m] = rt -> x;
if(rt++, rt != s.end()) temp[++m] = rt -> x;
}
sort(temp + , temp + m + , cmp);
if(m) gb[i] = temp[];
if(m > ) ga[i] = temp[];
}
t = log(n * 1.0) / log(2.0);
for(i = ; i <= n; i++){
if(ga[i]) dp[][i][] = ga[i], sta[][i][] = dist(ga[i], i), stb[][i][] = ;
if(gb[i]) dp[][i][] = gb[i], stb[][i][] = dist(gb[i], i), sta[][i][] = ;
}
for(i = ; i <= t; i++)
for(int j = ; j <= n; j++)
for(int k = ; k < ; k++){
int l;
if(i == ) l = k ^ ; else l = k;
if(dp[i - ][j][k]) dp[i][j][k] = dp[i - ][dp[i - ][j][k]][l];
if(dp[i][j][k]){
sta[i][j][k] = sta[i - ][j][k] + sta[i - ][dp[i - ][j][k]][l];
stb[i][j][k] = stb[i - ][j][k] + stb[i - ][dp[i - ][j][k]][l];
}
}
int X0;
scanf("%d", &X0); ansA = , ansB = ;
for(i = ; i <= n; i++){
solve(i, X0);
if(!lb) la = ;
if(la * ansB < lb * ansA || (la * ansB == lb * ansA && h[i] > h[ans]))
ansA = la, ansB = lb, ans = i;
}
printf("%d\n", ans);
scanf("%d", &m);
int x, y;
while(m--){
scanf("%d%d", &x, &y);
solve(x, y);
printf("%lld %lld\n", la, lb);
}
return ;
}
倍增优化DP就是一个划分状态+状态拼凑的过程