CF2103F Maximize Nor 题解

· · 题解

对我而言，Nor 是一个陌生的运算，所以很多性质需要慢慢发掘。

首先考虑如何得出答案：假如我们能得出一些优秀的区间，那么我们可以上一个线段树。假设区间的左右断点为 l 和 r，区间的 nor 值为 v，我们就把 ans_l 到 ans_r 和 v 取 max。

首先我们肯定要思考的一点是：如果给定了你一个区间，你会怎么快速求它的答案？显然先要拆位。

我们很快想到了一个性质：决定这一位是 0 还是 1，我们只用关心最后一段连续 0 的奇偶性。

于是我们能这么快速算：记 pre_{i,j} 表示在 i 前面（包含 i），最后一个满足“这个数第 j 位是 1”的下标，没有记为 0。

我们能发现一些性质：

如果 l>pre_{r,j}，那么第 j 位的值为 1，当且仅当 l 的奇偶性和 r 不同。

如果 l=pre_{r,j}，那么第 j 位的值为 1，当且仅当 l 的奇偶性和 r 相同。

如果 l<pre_{r,j}，那么第 j 位的值为 1，当且仅当 pre_{r,j} 的奇偶性和 r 不同。

这样我们就能快速算了。

你以为我们只迈出了第一步？不，我们快做完了！

我们考虑固定 r。注意到一些事实：

如果 l>pre_{r,j}，那么 l 到 r 的第 j 位和 l+2 到 r 的第 j 位是相同的。

如果 l<pre_{r,j}，那么 l 到 r 的第 j 位和 l-1 到 r 的第 j 位是相同的。也就是说这里和 l 没有关系了。

也就是说，如果我们固定了 r，那么区间权值的种类数是 O(k) 个的！

这就很厉害了，我们可以直接把 O(n^2) 个区间变成 O(nk) 个区间。

总体时间复杂度 O(nk\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
const int mod=1e9+7;
int n,k;
int a[N];
int pre[N][18];
int nor(int l,int r){
    int ans=0;
    for(int i=0;i<k;i++){
        if(pre[r][i]<l&&l%2!=r%2)ans|=1<<i;
        if(pre[r][i]==l&&l%2==r%2)ans|=1<<i;
        if(pre[r][i]>l&&pre[r][i]%2!=r%2)ans|=1<<i;
    }
    return ans;
}
namespace SegmentTree{
    int t[N<<2];
    int lazy[N<<2];
    #define ls(p) p<<1
    #define rs(p) p<<1|1
    void clear(int n){
        for(int i=1;i<=4*n;i++)t[i]=lazy[i]=0;
        return;
    }
    void push_up(int p){
        t[p]=max(t[ls(p)],t[rs(p)]);
        return;
    }
    void build(int l,int r,int p){
        if(l==r){
            t[p]=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,ls(p));
        build(mid+1,r,rs(p));
        push_up(p);
        return;
    }
    void addlazy(int p,int x){
        t[p]=max(t[p],x);
        lazy[p]=max(lazy[p],x);
        return;
    }
    void push_down(int p){
        if(!lazy[p])return;
        addlazy(ls(p),lazy[p]);
        addlazy(rs(p),lazy[p]);
        lazy[p]=0;
        return;
    }
    void update(int L,int R,int x,int l,int r,int p){
        if(L>R)return;
        if(L<=l&&r<=R){
            addlazy(p,x);
            return;
        }
        push_down(p);
        int mid=(l+r)>>1;
        if(L<=mid)update(L,R,x,l,mid,ls(p));
        if(R>mid)update(L,R,x,mid+1,r,rs(p));
        push_up(p);
        return;
    }
    int query(int D,int l,int r,int p){
        if(l==r)return t[p];
        push_down(p);
        int mid=(l+r)>>1;
        if(D<=mid)return query(D,l,mid,ls(p));
        return query(D,mid+1,r,rs(p));
    }
}
using namespace SegmentTree;
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    clear(n);
    build(1,n,1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<k;j++){
            if((a[i]>>j)&1)pre[i][j]=i;
            else pre[i][j]=pre[i-1][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<k;j++){
            for(int p=-2;p<=2;p++){
                if(pre[i][j]+p<1||pre[i][j]+p>n)continue;
                update(pre[i][j]+p,i,nor(pre[i][j]+p,i),1,n,1);
            }
        }
        update(1,i,nor(1,i),1,n,1);
    }
    for(int i=1;i<=n;i++)cout<<query(i,1,n,1)<<" ";
    cout<<"\n";
    for(int i=1;i<=n;i++)for(int j=0;j<k;j++)pre[i][j]=0;
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int Tc=1;
    cin>>Tc;
    while(Tc--)solve();
    return 0;
}