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

· · 题解

Solution

哎这个真的很套路吗。

首先考虑 l=1 且 r=n 咋做。这种二进制问题，考虑按位贪。建出一个 01 trie 树，考虑依次决策每一位。

当 trie 树这一位只有 1 个儿子的时候，我们可以控制答案这一位是 1；否则，我们要在两个子树中选一个出来作为这一位是 0，那么显然选的是较大值。

也就是说，我们是这样一个树形 DP：设 dp_{u} 表示考虑 u 的子树中能得到的最大答案。则

dp_u = \max\{dp_{ls},dp_{rs}\}

或

dp_u = dp_s + 2^d

直接莫队的话，似乎可以做到 O(nm \sqrt q)，应该过不去。

将所有的 \max 拆开，等价于：选一个根到叶子的路径。如果路径上一点没有邻居，那么会带来 2^d 的贡献。

发现我们可以维护出这个数每一位，左边和右边第一个邻居的位置 l_d 和 r_d。这样如果询问的 l 和 r 满足 l_d < l \le r < r_d 那么就可以带来 2^d 的贡献。

所以对于每个位置来说，他只有 O(m^2) 个本质不同的区间。然后查询相当于一个二维数点问题，所以你可以做到 O(q \log n + n m^2 \log n)。

但是这样有点魔怔了，因为你发现查询本质上是 2-side 矩形，而且 nm^2 远大于 q。所以考虑使用值域分块来平衡一下复杂度，做到 O(q \sqrt n + nm^2)，足以通过本题。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10,B=320;
int n,m,q,l[MAXN][55],r[MAXN][55];
ll a[MAXN];
vector<pair<int,ll>> u1[MAXN],u2[MAXN]; 
namespace ZYFK {
    int L[MAXN],R[MAXN],bel[MAXN];
    ll mx1[MAXN],mx2[MAXN];
    void init(void) {
        int k=(n+B-1)/B;
        ffor(i,1,k) L[i]=R[i-1]+1,R[i]=min(n,i*B);
        ffor(i,1,k) ffor(j,L[i],R[i]) bel[j]=i;
        return ;
    }
    void update(int pos,ll v) {
        mx1[pos]=max(mx1[pos],v),mx2[bel[pos]]=max(mx2[bel[pos]],v);
        return ;    
    }
    ll query(int pos) {
        ll ans=0;
        ffor(i,1,bel[pos]-1) ans=max(ans,mx2[i]);
        ffor(i,L[bel[pos]],pos) ans=max(ans,mx1[i]);
        return ans; 
    }
};
vector<pair<int,int>> qr[MAXN];
ll ans[MAXN*5];

int tot=1,tr[MAXN*50][2],vis[MAXN*50];
void insert(ll v) {
    int u=1;
    roff(i,m-1,0) {
        int op=!!(v&(1ll<<i));
        if(!tr[u][op]) tr[u][op]=++tot;
        u=tr[u][op];
    }
    return ;
}
void mark(ll v,int id) {
    int u=1;
    roff(i,m-1,0) {
        int op=!!(v&(1ll<<i));
        vis[u]=id,u=tr[u][op];  
    }
    vis[u]=id;
    return ;
}
void solve1(ll v,int id) {
    int u=1;
    roff(i,m-1,0) {
        int op=!!(v&(1ll<<i));
        if(!tr[u][op^1]||vis[tr[u][op^1]]==0) l[id][i]=0;
        else l[id][i]=vis[tr[u][op^1]];
        u=tr[u][op];
    }
    return ;
}
void solve2(ll v,int id) {
    int u=1;
    roff(i,m-1,0) {
        int op=!!(v&(1ll<<i));
        if(!tr[u][op^1]||vis[tr[u][op^1]]==0) r[id][i]=n+1;
        else r[id][i]=vis[tr[u][op^1]];
        u=tr[u][op];
    }
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q>>m;
    ffor(i,1,n) cin>>a[i];
    ffor(i,1,n) insert(a[i]);
    ffor(i,1,n) solve1(a[i],i),mark(a[i],i);
    memset(vis,0,sizeof(vis));
    roff(i,n,1) solve2(a[i],i),mark(a[i],i);
    ffor(i,1,n) {
        vector<pair<int,int>> vl;
        ffor(j,0,m-1) vl.push_back({l[i][j],j});
        sort(vl.begin(),vl.end(),[](pair<int,int> A,pair<int,int> B) {
            return A>B;
        });
        int pos=0;
        ll ov=0;
        while(pos<vl.size()) {
            int id=vl[pos].first;
            if(id==0) break ;
            u1[i].push_back({id,ov});
            while(pos<vl.size()&&vl[pos].first==id) ov|=(1ll<<vl[pos].second),pos++;
        }
        u1[i].push_back({0,ov});
        pos=0,ov=0,vl.clear();
        ffor(j,0,m-1) vl.push_back({r[i][j],j});
        sort(vl.begin(),vl.end());
        while(pos<vl.size()) {
            int id=vl[pos].first;
            if(id==n+1) break ;
            u2[id-1].push_back({i,ov});
            while(pos<vl.size()&&vl[pos].first==id) ov|=(1ll<<vl[pos].second),pos++;
        }
        u2[n].push_back({i,ov});
    }
    ZYFK::init();
    ffor(i,1,q) {
        int l,r;
        cin>>l>>r,qr[r].push_back({l,i});   
    }
    roff(i,n,1) {
        for(auto pr:u2[i]) {
            int id=pr.first;
            ll Ov=pr.second;
            for(auto ppr:u1[id]) {
                int ul=ppr.first;
                ll ov=Ov;
                ov|=ppr.second,ov^=(1ll<<m)-1;
                ZYFK::update(ul+1,ov);  
            }
        }
        for(auto pr:qr[i]) ans[pr.second]=ZYFK::query(pr.first);
    }
    ffor(i,1,q) cout<<ans[i]<<'\n';
    return 0;
}