题解：P12573 [UOI 2023] An Array and XOR

· · 题解

P12573 [UOI 2023] An Array and XOR

在博客食用阅读体验更佳。

题意：

给定长为 n 的序列 a，值域在 [0,2^m) 内，q 次询问 l,r，定义 f(x) 为 x 异或序列 a_{i \in [l,r]} 的结果的最小值，询问 \max_{x \in [0,2^m-1]}f(x)。

思路：

对二进制下每一位来观察，若区间内每个数第 j 位都相同，则令 x 第 j 位取相反值可以使最终结果这一位为 1，否则由于取最小异或值的这一位为 0。

想到建出 trie 树，区间内某一位的取值种类转化为树上节点的儿子数，令 dp_u 表示 u 子树内异或值的最大值，则可以得到转移方程，设当前位为 w，当有两个儿子时，dp_u = \max(dp_{ls},dp_{rs})，只有一个儿子时 dp_x=dp_s+2^w。

既然有 q 次询问，支持离线，不难想到莫队，令 trie 树支持插入和删除，我们可以单次做到 O(m) 修改 dp 值，这样我们就做到了 O(nm \sqrt q) 的复杂度，这是无法通过的，代码放在博客里。

既然要求某一位在区间内没有不同的值才能产生贡献，那么我们可以通过正反扫描一遍 trie 处理出每个数的每一位前面和后面最近的一个和他不一样的位置，分别记作 fl 和 fr。

那么只有对于 l<fl_{i,j} 且 fr_{i,j}<r 的询问，j 这一位才可以贡献答案。

不妨对右端点从大到小做扫描线，每扫到一个 fr_{x}-1，说明 x 可以开始贡献，为了保证正确性，按照 fl_{x,j} 从小到大来枚举 j，令当前能贡献的值为 cur，cur 依次或上 2^j，再把 cur 加入到数据结构的 fl_{x,j}+1 这个位置上。

当扫到询问的右端点 r 时，向数据结构询问 [1,l] 的最大值。

使用线段树或树状数组的话，单次询问和修改都是 O(\log n) 的，故而总时间复杂度为 O(nm^2 \log n+q \log n)，但是因为 nm^2 过大所以无法通过，代码在博客里。

然后我们为了平衡修改和查询的复杂度，考虑使用分块。分块维护最大值只要 O(1) 修改，O(\sqrt n) 查询，所以总时间复杂度 O(nm^2+q \sqrt n)，可以通过。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
inline int read(){
    int k=0,f=1,c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())k=k*10+(c^48);
    return k*f;
}
inline void write(int x){
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
int n,m,k,t;
const int N = 1e5+10;
int a[N],ans[5*N];
int fl[N][55],fr[N][55],p[N][55];
struct trie{
    int t[N*55][2],tot;
    vector<int>v[55*N];
    void init(){
        for(int i=0;i<=tot;i++){
            t[i][0]=t[i][1]=0;
            v[i].clear();
        }
        tot=0;
    }
    void ins(int x,int id,bool typ){
        int p=0;
        for(int w=m-1;w>=0;w--){
            int mk=(x>>w)&1ll;
            if(!t[p][mk])t[p][mk]=++tot;
            for(auto u:v[t[p][mk^1]]){
                if(typ)fr[u][w]=id;
                else fl[u][w]=id;
            }
            v[t[p][mk^1]].clear();
            v[t[p][mk]].push_back(id);
            p=t[p][mk];
        }
    }
}T;
int val[55];
bool cmp(int x,int y){
    return val[x]<val[y];
}
struct qy{
    int l,id;
};
vector<qy>q[N];
vector<int>s[N];
int L[N],R[N],pos[N],mx[N],kmx[N];
void change(int l,int v){
    mx[l]=max(mx[l],v);
    kmx[pos[l]]=max(kmx[pos[l]],v);
}
int query(int l,int r){
    int p=pos[l],q=pos[r];
    if(p==q){
        int ans=0;
        for(int i=l;i<=r;i++)ans=max(ans,mx[i]);
        return ans;
    }
    int ans=0;
    for(int i=l;i<=R[p];i++)ans=max(ans,mx[i]);
    for(int i=p+1;i<q;i++)ans=max(ans,kmx[i]);
    for(int i=L[q];i<=r;i++)ans=max(ans,mx[i]);
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    n=read(),k=read(),m=read();
    t=sqrt(n);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*t+1;
        R[i]=i*t;
    }
    if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
    for(int i=1;i<=t;i++){
        for(int j=L[i];j<=R[i];j++)pos[j]=i;
    }
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    T.init();
    for(int i=1;i<=n;i++){
        T.ins(a[i],i,1);
    }
    T.init();
    for(int i=n;i>=1;i--){
        T.ins(a[i],i,0);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            p[i][j]=j;
            if(!fr[i][j])fr[i][j]=n+1;
            fl[i][j]++;fr[i][j]--;
            s[fr[i][j]].push_back(i);
            val[j]=fl[i][j];
        }
        sort(p[i],p[i]+m,cmp);
    }
    for(int i=1;i<=k;i++){
        int l,r;
        l=read(),r=read();
        q[r].push_back({l,i});
    }
    for(int i=n;i>=1;i--){
        for(auto v:s[i]){
            int cur=0;
            for(int j=0;j<m;j++){
                int x=p[v][j];
                if(fr[v][x]>=i){
                    cur|=(1ll<<x);
                }
                change(fl[v][x],cur);
            }
        }
        for(auto [l,id]:q[i]){
            ans[id]=query(1,l);
        }
    }
    for(int i=1;i<=k;i++){
        write(ans[i]);
        putchar(endl);
    }
    return 0;
}