法老找来的题，说是找了三道 其他模拟赛的 T4 拼成 T1~T3，另外搞了道 T4。
思维好题，但是放在 T1 有点搞心态，但是还好大样例够强，400 没挂。
然而 T3 大样例输出错了，浪费了我 0.5h，
差评。
首先发现向左走之后向右走是一定不优的，所以最短路的情况只能先向右再向左。
考虑枚举起点 \(s\)，分两步转移 \(s\to u\) 的最短距离 \(f_u\)。
向右走
转移为 \(f_i=\min\limits_{j=b_i}^{i-1}\{f_j\}+1\)。
容易想到 \(O(n\log n)\) 的做法，但是这里考虑 \(O(n)\)。
记 \(g_x=\max\limits_{f_i=x}\{i\}\)。
那么 \(f_i=\min\limits_{g_x \ge b_i}\{x\}\)。
由于 \(b_i<i\)，所以 \(f_i\le f_{i-1}+1\)。
下面证明单调性：
- 记
- 此时
- 得到
- 归纳得到：
所以在 \(i\) 的时候，可以从 \(f_{i-1}+1\) 开始向下枚举 \(f_i\)，不合法时直接 break，做到均摊 \(O(n)\)。
向左走
可以在原来的 \(f\) 数组上继续 dp。
转移为：\(f'_i=\min\{f_i,\min\limits_{a_j\le i<j}\{f'_j\}\}\)，下面考虑后一项的。
一样的套路，记 \(g_x=\min\limits_{f_i=x}\{a_i\}\)。
转移变为：\(f'_i=\min\limits_{g_x\le i}\{x\}\)。
也能够证明单调性：
- 如果 \(g_{x-1}\le i,g_{x}>i\)，那么 \(f'_{i+1}\le x\)
- 若 \(f'_{i+1}=x\)，那么 \(g_x\le a_{i+1}\le i\)，不符合；
- 若 \(f'_{i+1}<x\)，那么由于 \(f'_{i}\le f'_{i+1}+1\le x\)，所以无需考虑上界 \(x\)。
- 所以 \(g_{x-1}\le i\Longrightarrow g_x\le i\)，单调性得到证明。
所以 \(f'_i\) 直接从 \(f'_{i+1}+1\) 开始向下枚举验证即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=6e3+10,INF=1e9;
int n,a[N],b[N];
int pos[N],f[N];
int ans;
void solve(int s){
fill(f+1,f+1+n,INF),f[s]=0;
fill(pos,pos+1+n,0),pos[0]=s;
for(int i=s+1,x=0;i<=n;i++){
x++;
for(;x>0&&pos[x-1]>=b[i];x--);
pos[f[i]=x+1]=i;
}
fill(pos,pos+1+n,n+1);
for(int i=n,x=INF;i>=1;i--){
x=min(x+1,f[i]);
for(;x>0&&pos[x-1]<=i;x--);
f[i]=min(f[i],x+1);
pos[f[i]]=min(pos[f[i]],a[i]);
}
for(int i=1;i<=n;i++)ans^=f[i]*(i+s);
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++)scanf("%d",&a[i]);
for(int i=2;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++)solve(i);
cout<<ans;
return 0;
}