太菜了太菜了，日常被1800吊锤

题目大意：

给出 f ( b ) f(b) f(b)的递归定义：


然后进行 Q Q Q次询问，每次询问区间 [ l , r ] [l,r] [l,r]内，所有子区间 [ x , y ] [x,y] [x,y]的 f ( a [ x : y ] ) f(a[x:y]) f(a[x:y])的最大值

题目思路：

以为很简单的题…(确实简单)

被卡了，主要原因是忽略了题目给出的定义。

第一眼看到这个题可能没什么思路，但仔细理一下题目的定义会发现：

x 1 ⊕ x 2 ⊕ x 3 ⊕ x 4 ⊕ x 5 x_1⊕ x_2⊕ x_3⊕ x_4 ⊕x_5 x1​⊕x2​⊕x3​⊕x4​⊕x5​
x 1 ⊕ x 2 ∣ x 2 ⊕ x 3 ∣ x 4 ⊕ x 5 x_1⊕ x_2 | x_2⊕ x_3 | x_4⊕x_5 x1​⊕x2​∣x2​⊕x3​∣x4​⊕x5​
x 1 ⊕ x 2 ⊕ x 2 ⊕ x 3 ∣ x 2 ⊕ x 3 ⊕ x 4 ⊕ x 5 x_1⊕ x_2⊕ x_2⊕x_3 |x_2⊕x_3 ⊕x_4⊕x_5 x1​⊕x2​⊕x2​⊕x3​∣x2​⊕x3​⊕x4​⊕x5​
x 1 ⊕ x 2 ⊕ x 2 ⊕ x 3 ⊕ x 2 ⊕ x 3 ⊕ x 4 ⊕ x 5 x_1⊕ x_2⊕ x_2⊕x_3⊕x_2⊕x_3 ⊕x_4⊕x_5 x1​⊕x2​⊕x2​⊕x3​⊕x2​⊕x3​⊕x4​⊕x5​

显然规律:

d p [ i ] [ k ] = d p [ i − 1 ] [ k ] ⊕ d p [ i − 1 ] [ k + 1 ] dp[i][k] = dp[i-1][k] ⊕dp[i-1][k+1] dp[i][k]=dp[i−1][k]⊕dp[i−1][k+1]

也就是说第 i i i层的第 j j j个位置的值为 d p [ i ] [ j ] dp[i][j] dp[i][j]

设 f [ l ] [ r ] f[l][r] f[l][r]代表区间 [ l , r ] [l,r] [l,r]的异或值，写一下规律就会发现，每个区间到最后的值都对应着 d p dp dp数组某层的某个节点。

很明显推出来:

f [ l ] [ r ] = d p [ r − l + 1 ] [ l ] f[l][r] = dp[r-l+1][l] f[l][r]=dp[r−l+1][l]

然后所有的区间的异或值也就得出来了，得出来后，只需要将区间扩充一下就好了。

经典规律题不会了.

/*** keep hungry and calm CoolGuang!  ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const int M = 1e6+8;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int dp[5005][5005],f[5005][5005];
int a[maxn];
int main(){
  read(n);
  for(int i=1;i<=n;i++) read(a[i]);
  for(int k=1;k<=n;k++) dp[1][k] = a[k];
  for(int i=2;i<=n;i++)
    for(int k=1;k<=n-i+1;k++)
      dp[i][k] = dp[i-1][k]^dp[i-1][k+1];
  for(int i=1;i<=n;i++) f[i][i] = a[i];
  for(int len=1;len<=n-1;len++){
    for(int s=1;s+len<=n;s++){
      int t = s+len;
      f[s][t] = max(f[s+1][t],f[s][t-1]);
      f[s][t] = max(f[s][t],dp[len+1][t-len]);
    }
  }
  read(m);
  for(int i=1;i<=m;i++){
    int x,y;read(x);read(y);
    if(x>y) swap(x,y);
    di(f[x][y]);
  }
  return 0;
}