Description：

设 $f(b)=b[1](m=1)/f(b[1]\text{ xor }b[2],b[2]\text{ xor }b[3],\dots,b[m-1]\text{ xor }b[m])(m\ne 1)$ 。

给一个数列， $q$ 次询问每次给出一个区间询问最大区间 $f$ 和。

$1\le n \le 5000,1\le q \le 100000$

Solution：

首先证明一个结论： $f(1\sim n)=f(1\sim n-1)\text{ xor }f(2\sim n)$ 。

首先 $f(b[1],b[2])=f(b[1]\text{ xor }b[2])=b[1]\text{ xor }b[2]=f(b[1])\text{ xor }f(b[2])$ 。

下面证明若长度为 $m-1$ 的序列都满足，那么长度为 $m$ 的序列也满足。

$f(b[1],b[2],\dots,b[m])=f(b[1]\text{ xor }b[2],b[2]\text{ xor }b[3],\dots,b[m-1]\text{ xor }b[m])$ ，可以应用数学归纳法，原式 $=f(b[1]\text{ xor }b[2],b[2]\text{ xor }b[3],\dots,b[m-2]\text{ xor }b[m-1])\text{ xor }f(b[2]\text{ xor }b[3],b[3]\text{ xor }b[4],\dots,b[m-1]\text{ xor }b[m])$

那么原式 $=f(b[1],b[2],\dots,b[m-1])\text{ xor }f(b[2],b[3],\dots,b[m])$ 。

所以先区间 $DP$ 出每个区间的 $f$ 值，然后 $dp[i][j]=\max(f[i][j],\max(f[i][j-1],f[i+1][j]))$ 预处理出每个区间的子段最大值，询问时直接处理即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,q;

#define MAXN 5010

int f[MAXN][MAXN];

int g[MAXN][MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&f[i][i]);

	for(int i = 1;i <= n;++i)g[i][i] = f[i][i];

	for(int l = 2;l <= n;++l)

	{

		for(int i = 1;i <= n - l + 1;++i)

		{

			int j = i + l - 1;

			f[i][j] = f[i + 1][j] ^ f[i][j - 1];

			g[i][j] = max(f[i][j],max(g[i + 1][j],g[i][j - 1]));

		}

	}

	scanf("%d",&q);

	int a,b;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&a,&b);

		printf("%d\n",g[a][b]);

	}

	return 0;

}