题解：P17209 「DLESS-6」XOR and Your Problem

· · 题解

提供一种根号分块和压位 Trie 以外的瞎搞做法。

记

F(l,r)=\max_{l\le i<j\le r}(a_i\mathbin{\mathrm{xor}}a_j),

长度为 1 时令答案为 0。考虑按照右端点 r 从小到大扫，扫到 r 时只需要加入所有以 r 结尾的新数对。

固定 x=a_r，令

w_i=a_i\mathbin{\mathrm{xor}}x\qquad(1\le i<r).

对于左端点 l，这次新加入的答案就是

\max_{l\le i<r}w_i.

如果从右往左扫 w_i，显然只有严格刷新后缀最大值的位置才可能有用。比如当前右边已经出现的最大值为 out，若 w_i\le\text{out}，那么把左端点放到 i 也不会产生新答案。

还可以再砍一层。设扫到 r 之前已经有

H_i=F(i,r-1).

即使 w_i 刷新了后缀最大值，只要 w_i\le H_i，它仍然会被之前的答案盖掉。于是以 r 为右端点、真正需要记录的位置恰好满足

w_i>\max_{i<j<r}w_j,\qquad w_i>F(i,r-1).

也可以把这样的 [i,r] 看成一个关键区间：删掉左端点或右端点都会让区间最大异或下降。任意询问都能不断删掉无用的端点，最后缩到某个关键区间，所以只保存这些区间不会漏答案。

接下来用一棵反着写的 Fenwick 树保存它们。发现关键区间 [i,r]、答案为 v 时，在位置 i 做一次 chmax；查询左端点 l 时取所有位置 i\ge l 的最大值。代码就是

void add(int x,int v){for(;x;x-=x&-x)bit[x]=max(bit[x],v);}
int ask(int x){int z=0;for(;x<=n;x+=x&-x)z=max(z,bit[x]);return z;}

扫到 r 以前，ask(i) 正好等于 F(i,r-1)；把这轮找到的关键区间全部加入以后，ask(l) 就变成 F(l,r)。因此询问按右端点挂链，扫到对应位置时直接回答即可。

问题只剩不能真的对每个 r 都把前面的 w_i 扫一遍。

写一个 work(l,r,out,x)，其中 out 表示位置 r 右边已经出现的最大异或值。先求

mx=\max_{l\le i\le r}(a_i\mathbin{\mathrm{xor}}x).

有两种情况可以整段退出：

否则把区间从中间分开，先递归右半边，再把右半边得到的新 out 带到左半边。一定要先右后左，因为我们模拟的本来就是从右往左扫。父区间的最大值已经算过，右半边再查一次以后，若父区间最大值仍大于 out，它就只能来自左半边，因此左递归连最大值查询都能省掉一次。

区间很短时继续递归反而亏，所以长度不超过某个值就直接倒着扫。这里用了一个 CUT=64，换成附近的数一般也都能跑，只是常数有点区别。

最后需要支持固定 x 的区间最大异或。这里用 Wavelet Matrix 从高位到低位稳定划分整个序列，每一层记录当前顺序中 1 的前缀数量。查询时优先进入与 x 当前位不同且区间非空的儿子，否则进入同位儿子。每层只做常数次前缀差，一次 farthest 是 O(30)。

:::info[这个做法到底有多瞎]

正确性没有随机成分，work 跳过的区间要么不可能刷新后缀最大值，要么一定被旧答案覆盖。

若记所有 work 实际访问的分治结点数为 V，小块中直接扫描的元素总数为 S，最后真正加入的关键区间数为 E，那么查询阶段可以比较诚实地写成

O(30V+S+(E+q)\log n).

关键区间本身可以按异或 Trie 的层数摊到 O(30n)，但 V,S 的实际大小仍很依赖剪枝和 CUT，所以我更愿意把它叫输出敏感瞎搞。预处理 Wavelet Matrix 为 O(30n)，空间复杂度为 O(30n+q)。

:::

下面是实现：

#include<bits/stdc++.h>
using namespace std;
const int N=300005,K=30,CUT=64;
int sm[K][N],a[N],bit[N],head[N],ql[N],nxt[N],ans[N],n;
void add(int x,int v){for(;x;x-=x&-x)bit[x]=max(bit[x],v);}
int ask(int x){int z=0;for(;x<=n;x+=x&-x)z=max(z,bit[x]);return z;}
int farthest(int l,int r,int x){
    int s=0,z=n,L=l-1,R=r,res=0;
    for(int k=K-1;k>=0;k--){
        int p0=sm[k][s+L]-sm[k][s],p1=sm[k][s+R]-sm[k][s];
        int one=sm[k][s+z]-sm[k][s],zero=z-one,w=x>>k&1;
        if(!w){
            if(p0<p1){res|=1<<k;s+=zero;z=one;L=p0;R=p1;}
            else z=zero,L-=p0,R-=p1;
        }else{
            int zl=L-p0,zr=R-p1;
            if(zl<zr){res|=1<<k;z=zero;L=zl;R=zr;}
            else s+=zero,z=one,L=p0,R=p1;
        }
    }
    return res;
}
vector<pair<int,int> >up;
#ifdef LOCAL
long long calls,farq,ess;
#endif
int work(int l,int r,int out,int x,int w=-1,int h=-1){
    if(l>r)return out;
#ifdef LOCAL
    calls++;
#endif
    if(w<0){w=farthest(l,r,x);
#ifdef LOCAL
        farq++;
#endif
    }
    if(w<=out)return out;
    if(h<0)h=ask(r);
    if(w<=h)return w;
    if(r-l+1<=CUT){
        for(int i=r;i>=l;i--){
            int z=a[i]^x;
            if(z>out){if(z>ask(i))up.push_back({i,z});out=z;}
        }
        return out;
    }
    int m=(l+r)>>1;
    int rw=farthest(m+1,r,x);
#ifdef LOCAL
    farq++;
#endif
    out=work(m+1,r,out,x,rw,h);
    if(w<=out)return out;
    return work(l,m,out,x,w);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int q;cin>>n>>q;
    vector<int>b(n),c(n);for(int i=1;i<=n;i++)cin>>a[i],b[i-1]=a[i];
    vector<pair<int,int> >blk(1,{0,n}),nb;
    for(int k=K-1;k>=0;k--){
        for(int i=0;i<n;i++)sm[k][i+1]=sm[k][i]+(b[i]>>k&1);
        nb.clear();
        for(pair<int,int>z:blk){
            int l=z.first,r=z.second,p=l;
            for(int i=l;i<r;i++)if(!(b[i]>>k&1))c[p++]=b[i];
            int m=p;
            for(int i=l;i<r;i++)if(b[i]>>k&1)c[p++]=b[i];
            if(l<m)nb.push_back({l,m});
            if(m<r)nb.push_back({m,r});
        }
        b.swap(c);blk.swap(nb);
    }
    vector<int>().swap(b);vector<int>().swap(c);
    vector<pair<int,int> >().swap(blk);vector<pair<int,int> >().swap(nb);
    memset(head,-1,sizeof(int)*(n+1));
    for(int i=0,r;i<q;i++)cin>>ql[i]>>r,nxt[i]=head[r],head[r]=i;
    for(int r=1;r<=n;r++){
        up.clear();if(r>1)work(1,r-1,-1,a[r]);
        for(pair<int,int>z:up)add(z.first,z.second);
#ifdef LOCAL
        ess+=up.size();
#endif
        for(int i=head[r];i!=-1;i=nxt[i])ans[i]=ask(ql[i]);
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
#ifdef LOCAL
    cerr<<"calls "<<calls<<" far "<<farq<<" essential "<<ess<<"\n";
#endif
}