P14188 [ICPC 2024 Hangzhou R] Barkley III TJ

· · 题解

闲话

感谢同机房 @zhangchi1234 大佬给的后半段思路。

思路

看到这种需要最大化某种东西的位运算题目先考虑从高位往低位枚举，发现如果我们只有一个数在枚举到的这一位上是 0，其余全是 1，那么此时我们选择这个数一定是最优的。

于是考虑如何维护，一个很简单的想法是拆位统计一个区间有多少数字在某一位上为 1，用线段树并在查找数的位置时树上二分即可，但这样是 O(\log^2n) 的，考虑优化。

我自己想到这就不会了，以下是 @zhangchi1234 大佬的方法：

发现事实上我们只关心某一位是否至少有一个 0 以及是否至少有两个 0，这个直接用两个 01 变量即可维护，为了方便我们将其压成两个数 s1,s2，那么转移如下：

x_{s2}=l_{s2}\operatorname{or}r_{s2}\operatorname{or}(l_{s1}\operatorname{and}r_{s1})

在初始化时 x_{s1}=\operatorname{not}a_i,x_{s2}=0。

操作 2 要注意若当前节点区间 l = r 那么不要修改 s_2。

Code

#include <bits/stdc++.h>
#define int long long
#define INF LONG_LONG_MAX
#define maxn 1000005
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
struct node{
    int s1,s2,s3,flg,siz;
}e[maxn<<2];
int n,q,a[maxn],op,l,r,x,y;
void push_up(int x){
    e[x].s1 = e[x<<1].s1&e[x<<1|1].s1;
    e[x].s2 = e[x<<1].s2|e[x<<1|1].s2;
    e[x].s3 = e[x<<1].s3|e[x<<1|1].s3|(e[x<<1].s2&e[x<<1|1].s2);
}
void giveflg(int id,int x){
    e[id].s1 &= x,e[id].s2 |= (INF^x),e[id].s3 |= (e[id].siz == 1 ? 0 : (INF^x)),e[id].flg &= x;
}
void push_down(int id){
    if (e[id].flg == INF) return;
giveflg(id<<1,e[id].flg),giveflg(id<<1|1,e[id].flg);
    e[id].flg = INF;
}
void init(int l,int r,int x){
    e[x].flg = INF;
    if (l == r) e[x].s1 = a[l],e[x].s2 = INF^a[l],e[x].s3 = 0,e[x].siz = 1;
    else{
        int mid = l + (r - l >> 1);
        init(l,mid,x<<1),init(mid+1,r,x<<1|1);
        e[x].siz = e[x<<1].siz+e[x<<1|1].siz;
        push_up(x);
    }
}
void change(int l,int r,int x,int y,int id){
    if(l == r) e[id].s1 = y,e[id].s2 = INF^y,e[id].s3 = 0;
    else{
        int mid = l + (r - l >> 1);
        push_down(id);
        if (x <= mid) change(l,mid,x,y,id<<1);
        else change(mid+1,r,x,y,id<<1|1);
        push_up(id);
    }
}
void update(int l,int r,int sl,int sr,int x,int id){
    if (sl <= l && r <= sr) giveflg(id,x);
    else{
        int mid = l + (r - l >> 1);
        push_down(id);
        if (sl <= mid) update(l,mid,sl,sr,x,id<<1);
        if (sr > mid) update(mid+1,r,sl,sr,x,id<<1|1);
        push_up(id);
    }
}
bool check(int s2,int s3,int x){
    return ((s2>>x&1) && !(s3>>x&1));
}
int findp(int l,int r,int ql,int qr,int x,int id){
    if (e[id].s1>>x&1) return 0;
    if (l == r) return l;
    int mid = l + (r - l >> 1);
    push_down(id);
    if (ql <= l && r <= qr){
        if (!(e[id<<1].s1>>x&1)) return findp(l,mid,ql,qr,x,id<<1);
        else return findp(mid+1,r,ql,qr,x,id<<1|1);
    }else{
        int t;
        if (ql <= mid){
            t = findp(l,mid,ql,qr,x,id<<1);
            if (t) return t;
        }
        if (qr > mid){
            t = findp(mid+1,r,ql,qr,x,id<<1|1);
            if (t) return t;
        }
    }
    return 0;
}
pii find(int l,int r,int ql,int qr,int id){
    if (ql <= l && r <= qr) return {e[id].s2,e[id].s3};
    else{
        int mid = l + (r - l >> 1);
        pii ans = {0,0};
        push_down(id);
        if (ql <= mid){
            pii t = find(l,mid,ql,qr,id<<1);
            ans.se |= t.se|(ans.fi&t.fi),ans.fi |= t.fi;
        }
        if (qr > mid){
            pii t = find(mid+1,r,ql,qr,id<<1|1);
            ans.se |= t.se|(ans.fi&t.fi),ans.fi |= t.fi;
        }
        return ans;
    }
}
int find2(int l,int r,int ql,int qr,int id){
    if (ql > qr) return INF; 
    if (ql <= l && r <= qr) return e[id].s1;
    else{
        int mid = l + (r - l >> 1),ans = INF;
        push_down(id);
        if (ql <= mid) ans &= find2(l,mid,ql,qr,id<<1);
        if (qr > mid) ans &= find2(mid+1,r,ql,qr,id<<1|1);
        return ans;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    cin >> n >> q;
    for (int i = 1;i <= n;i++) cin >> a[i];
    init(1,n,1);
    while (q--){
        cin >> op;
        if (op == 1) cin >> l >> r >> x,update(1,n,l,r,x,1);
        else if (op == 2) cin >> x >> y,change(1,n,x,y,1);
        else{
            int t1,t2,p = 0;
            cin >> l >> r;
            tie(t1,t2) = find(1,n,l,r,1);
            for (int i = 62;~i;i--){
                if (check(t1,t2,i)){
                    p = findp(1,n,l,r,i,1);
                    break;
                }
            }
            if (p == 0) cout << find2(1,n,l,r,1) << "\n";
            else cout << (find2(1,n,l,p-1,1)&find2(1,n,p+1,r,1)) << "\n";
        }
    }
    return 0;
}