题解：P8955 「VUSC」Card Tricks

· · 题解

前言

在练习整体二分的时候找到了这道，大力卡常后过了，顺便写篇题解。

思路

由于一个数或上另一个数，其结果必然不小于原数，所以满足单调性。

先想对于单个 a_x 如何二分求解。

设当前二分的区间为 [L,R]（下文令 mid=\displaystyle{\lfloor \frac{L+R}{2} \rfloor}）：

对于多个 a_i，我们需要进行多次二分，显然这是不可取的。

考虑整体二分，则我们需要快速对一个区间进行或运算，查询单点权值，可以使用线段树。

值得一提的是，这道题只需要单点查询，因此可以使用一个类似于标记永久化的方法，如果在区间取或的递归过程中，当前区间被需要操作的区间完全覆盖，则在该区间打上或标记，查询时一路向下求标记或起来的和即可。

还有这道题需要卡常，笔者卡了很久才从 90pts 到 100pts。

代码：

#include<bits/stdc++.h> 
using namespace std;
const int N=1e6+5;
namespace SGT{
    #define L (x<<1)
    #define R (x<<1|1)
    int l[N<<2],r[N<<2];
    int tag[N<<2];
    inline void build(int x,int lq,int rq){
        l[x]=lq;
        r[x]=rq;
        tag[x]=0;
        if(lq==rq)return;
        const int mid=lq+rq>>1;
        build(L,lq,mid);
        build(R,mid+1,rq);
    }
    inline void modify(int x,int lq,int rq,int k){
        if(lq<=l[x]&&r[x]<=rq){
            if(k)tag[x]|=k;
            else tag[x]=0;//便于快速清空线段树
            return;
        }
        const int mid=l[x]+r[x]>>1;
        if(lq<=mid)modify(L,lq,rq,k);
        if(rq>mid)modify(R,lq,rq,k);
    }
    inline int query(int x,int i){
        if(l[x]==r[x])return tag[x];
        const int mid=l[x]+r[x]>>1;
        int res=tag[x];
        if(i<=mid)res|=query(L,i);
        else res|=query(R,i);
        return res;
    }
    #undef L
    #undef R
}
using SGT::build;
using SGT::modify;
using SGT::query;

int q[N],ql[N],qr[N];
int n,Q,p,a[N];
int l[N],r[N],k[N];
int ans[N];

//整体二分板子
inline void solve(int vaL,int vaR,int lq,int rq){
    if(lq>rq)return;
    if(vaL==vaR){
        for(int i=lq;i<=rq;++i)
            ans[q[i]]=vaL;
        return;
    }
    const int mid=vaL+vaR>>1;
    int cntl=0,cntr=0;
    for(int i=vaL;i<=mid;++i)
        modify(1,l[i],r[i],k[i]);
    for(int i=lq;i<=rq;++i){
        const int k=query(1,q[i]);
        if((k|a[q[i]])>p){
            ql[++cntl]=q[i];
        }else{
            a[q[i]]|=k;
            qr[++cntr]=q[i];
        }
    }
    for(int i=vaL;i<=mid;++i)
        modify(1,l[i],r[i],0);//清空线段树
    for(int i=1;i<=cntl;++i)
        q[lq+i-1]=ql[i];
    for(int i=1;i<=cntr;++i)
        q[lq+cntl+i-1]=qr[i];
    solve(vaL,mid,lq,lq+cntl-1);
    solve(mid+1,vaR,lq+cntl,rq);
}

template<typename T>
inline void read(T &x){
    char c;
    x=0;
    int fu=1;
    c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')fu=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    x*=fu;
}
template<typename T>
inline void print(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

int main(){
    read(n);read(Q);read(p);
    for(register int i=1;i<=n;++i){
        read(a[i]);
        q[i]=i;
    }
    for(register int i=1;i<=Q;++i){
        read(l[i]);read(r[i]);read(k[i]);
    }
    build(1,1,n);
    solve(1,Q+1,1,n);
    for(register int i=1;i<=n;++i){
        if(ans[i]>Q)print(-1);
        else print(ans[i]);
        printf(" ");
    }
    return 0;
}