小 Q 与彼岸花
题意
给你n个数，m组询问，让你求出每组询问中在区间[L,R]上两个数最大的异或值。
思路
昨天晚上以为时间复杂度为5e5，一直想不到思路，就没写出来。
今天早上又看了一眼数据范围，是5e3...
我们可以把所有的情况都预处理出来。
我们可以用两层循环来枚举每一个区间[i,j].
比如当前的区间是[1,5],我们的最大值就是区间[1,4]的最大值和a[5]和前面四个数异或的最大值的比较。
然后用trie存储当前区间的值。
trie存储每一个数的二进制位，就可以logn求出当前数和前面数的最大异或值
然后每次转移就是ans[i,j]=max(ans[i][j-1],qurey[a[j]]).
代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int ans[5010][5010];
int a[5010];
int son[5010*31][2],idx;
void insert(int x)
{
    int p = 0; //
    for (int i = 12; i >= 0; i--)
    {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
int query(int x)
{
    int p = 0, ret = 0;
    for (int i = 12; i >= 0; i--)
    {
        int u = x >> i & 1;
        if (!son[p][!u])
        {
            p = son[p][u];
            ret = ret * 2 + u;
        }
        else
        {
            p = son[p][!u];
            ret = ret * 2 + !u;
        }
    }
    ret = ret ^ x;
    return ret;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1 ; i<=n ; i++) cin>>a[i];
    for(int i=1 ; i<=n ; i++)
    {
        memset(son,0,sizeof son);
        idx=0;
        for(int j=i ; j<=n ; j++)
        {
            insert(a[j]);
            ans[i][j]=max(ans[i][j-1],query(a[j]));
        }
    }
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<ans[l][r]<<endl;
    }
    return 0;
}