【?? 记录】P9696 [GDCPC2023] Swapping Operation

· · 题解

首先，如果 swap，那么 k 一定在 swap 的一对位置中间。

不妨提取出改变前缀 \operatorname{and} 值与后缀 \operatorname{and} 值的 \log 个关键点。

如果交换非两个关键点，对应的前缀/后缀权值不会变大，因此不优。

如果交换一个关键点，一个非关键点。不妨假设是枚举的前缀关键点 i 与非关键点 j，那么每个 k 对应权值应是（记 f(i,j) 为 [i,j] 区间 \operatorname{and} 值）：

(f(1,i-1)\operatorname{and} f(i+1,k)\operatorname{and} a_j)+(f(k+1,n)\operatorname{and}a_i)

枚举 i 后右边的值固定，而左边注意到 f(1,i-1)\operatorname{and} f(i+1,k) 的值只有 \log^2 V 种，可以对每种 O(n) 暴力枚举 j 处理。

如果交换两个关键点，暴力枚举后计算。

复杂度 O(n\log^2 V)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005,maxk=19,S=(1<<30)-1;
int n,m,T,ans;
int a[maxn],lg[maxn],st[maxk][maxn],pv[maxn],ispre[maxn],issuf[maxn],mx[maxn];
vector<int>pre,suf;
map<int,vector< pair<int,int> >>mp;
int query(int l,int r){
    if(l>r)
        return S;
    int k=lg[r-l+1];
    return st[k][l]&st[k][r-(1<<k)+1];
}
void calc(){
    pv[0]=S;
    for(int i=1;i<=n;i++)
        pv[i]=pv[i-1]&a[i];
    for(int i=n,v=S;i>1;i--){
        v&=a[i],ans=max(ans,pv[i-1]+v);
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n),ans=0,lg[0]=-1;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),st[0][i]=a[i],lg[i]=lg[i>>1]+1,ispre[i]=issuf[i]=0;
        for(int i=1;i<=18;i++)
            for(int j=1;j+(1<<i)-1<=n;j++)
                st[i][j]=st[i-1][j]&st[i-1][j+(1<<(i-1))];
        pre.clear(),suf.clear();
        for(int i=1,now=S;i<=n;now&=a[i],i++)
            if((now&a[i])<now)
                pre.emplace_back(i),ispre[i]=1;
        for(int i=n,now=S;i>=1;now&=a[i],i--)
            if((now&a[i])<now)
                suf.emplace_back(i),issuf[i]=1;
        calc();
        for(int i=0;i<pre.size();i++)
            for(int j=0;j<suf.size();j++)
                swap(a[pre[i]],a[suf[j]]),calc(),swap(a[pre[i]],a[suf[j]]);
        mp.clear();
        for(int i=0;i<pre.size();i++)
            for(int j=pre[i];j<n;j++){
                int v=query(1,pre[i]-1)&query(pre[i]+1,j);
                mp[v].emplace_back(make_pair(j+1,query(j+1,n)&a[pre[i]]));
            }
        for(map<int,vector<pair<int,int>>>::iterator it=mp.begin();it!=mp.end();it++){
            int v=it->first;
            mx[n+1]=-2e9;
            for(int i=n;i>=1;i--){
                mx[i]=mx[i+1];
                if(issuf[i]==0)
                    mx[i]=max(mx[i],v&a[i]);
            }
            vector<pair<int,int>>V=it->second;
            for(int i=0;i<V.size();i++)
                ans=max(ans,mx[V[i].first]+V[i].second);
        }
        mp.clear();
        for(int i=0;i<suf.size();i++)
            for(int j=1;j<suf[i];j++){
                int v=query(j+1,suf[i]-1)&query(suf[i]+1,n);
                mp[v].emplace_back(make_pair(j,query(1,j)&a[suf[i]]));
            }
        for(map<int,vector<pair<int,int>>>::iterator it=mp.begin();it!=mp.end();it++){
            int v=it->first;
            mx[0]=-2e9;
            for(int i=1;i<=n;i++){
                mx[i]=mx[i-1];
                if(ispre[i]==0)
                    mx[i]=max(mx[i],v&a[i]);
            }
            vector<pair<int,int>>V=it->second;
            for(int i=0;i<V.size();i++)
                ans=max(ans,mx[V[i].first]+V[i].second);
        }
        printf("%d\n",ans);
    }
    return 0;
}