[CF983B]XOR-pyramid
wangyitong
2018-09-20 15:47:50
[题面传送门](https://www.luogu.org/problemnew/show/CF983B)
离线做，预处理$ans[i][j]$表示$(i,j)$之间的答案。
可能只有我这个蒟蒻看题看了半天
~~（找规律大法好）~~
我们直接设$f[i][j]$为$ (i,j) $这一段的f函数的值。
因为我们显然发现这个大区间是由小区间贡献而来的。
直接枚举一个长度，然后做区间DP；
f[i][j]转移怎么做呢？
画图或者严谨这么都可以，懒得写了。~~(最关键的)~~(雾
$f[i][j]=f[i][j-1]$ xor $f[i+1][j];$
然后统计答案就是按照区间DP的正常操作：
$ans[i][j]=max(ans[i][j-1],ans[i+1][j]),f[i][j]);$
code
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<set>
#define ri register int
using namespace std;
template <class T> void in(T &x) {
x=0;
bool flag=0;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-')
flag=1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
if(flag)
x=-x;
}
int n,q,l,r;
int ans[6000][6000];
int f[6000][6000];
int main() {
in(n);
for(ri i=1; i<=n; ++i)
in(f[i][i]),ans[i][i]=f[i][i];
for(ri l=1; l<=n; ++l)
for(ri i=1; i<=n; ++i) {
int j=i+l;
if(j>n) continue;
f[i][j]=f[i][j-1]^f[i+1][j];
ans[i][j]=max(max(ans[i][j-1],ans[i+1][j]),f[i][j]);
}
in(q);
for(ri i=1; i<=q; ++i) {
in(l),in(r);
printf("%d\n",ans[l][r]);
}
return 0;
}
```