C++14(g++5.4) 解法, 执行用时: 1619ms, 内存消耗: 97376K, 提交时间: 2019-10-01 20:17:31

#include <bits/stdc++.h>

#define For(i, j, k) for (int i = j; i <= k; i++)
#define Forr(i, j, k) for (int i = j; i >= k; i--)

using namespace std;

const int N = 6010;

int A[N], B[N];
int ldis[N][N];

int n, ans;
int fa[N], dis[N];

int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

queue<int> q[N];

int main() {

	scanf("%d", &n);
	A[1] = B[1] = 1;
	For(i, 2, n) scanf("%d", &A[i]), assert(A[i] < i && A[i] >= 1);
	For(i, 2, n) scanf("%d", &B[i]), assert(B[i] < i && B[i] >= 1);
	For(i, 2, n) {
		ldis[i][i] = 0;
		int k = i;
		For(j, B[i], i - 1) {
			ldis[j][i] = 1;
			if (B[k] > B[j]) k = j;
		}
		For(j, 1, B[i] - 1) ldis[j][i] = ldis[j][k] + 1;
	}

	For(i, 1, n) {
		For(j, 1, n) fa[j] = j, dis[j] = n;
		For(j, i, n) q[dis[j] = ldis[i][j]].push(j);
		For(j, 0, n) while (!q[j].empty()) {
			int x = q[j].front(); q[j].pop();
			if (dis[x] < j) continue;
			for (int k = find(x - 1); k >= A[x]; k = find(k - 1)) {
				if (dis[k] > j + 1) dis[k] = j + 1, q[j + 1].push(k);
				fa[k] = k - 1;
			}
		}
		For(j, 1, n) ans ^= (i + j) * dis[j];
	}
	printf("%d\n", ans);

	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 336ms, 内存消耗: 141540K, 提交时间: 2020-04-02 20:52:46

#include<cstdio>
const int maxn=6010;
int n,a[maxn],b[maxn],up[maxn],left[maxn];
struct item
{
	short x,y;
}Q[maxn*maxn],*h=Q,*t=Q;
int ans;
void ins(int x,int y,int d)
{
	if(y<x&&y<left[x])
	{
		while(left[x]>y) *t++=(item){(short)x,(short)--left[x]},ans^=d*(x+left[x]); 
		left[x]=y;
	}
	else if(x<y&&x<up[y])
	{
		while(up[y]>x) *t++=(item){(short)--up[y],(short)y},ans^=d*(up[y]+y);
		up[y]=x;
	}
}
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);
	a[1]=b[1]=1;
	for(int i=1;i<=n;i++)
	up[i]=left[i]=i,*t++=(item){(short)i,(short)i};
	for(int d=1;h<t;d++)
	{
		item*lim=t;
		for(;h<lim;h++)
		{
			ins(h->x,a[h->y],d);
			ins(b[h->x],h->y,d);
		}
	}
	printf("%d\n",ans);
}