给刚学整体二分的 OIer 们的题解

本蒟蒻看了一下午，终于把大佬们的题解看懂了。。。本篇题解借鉴其他 dalao 们的思路，会将思路和代码都做详细的解释，方便和我一样的~神犇~理解。

题意：

给出一个长度为

n

的序列

{a_n}

，然后给出

q

次修改，每次修改将区间

[L,R]

的每一个元素都“|”上一个值

v_i

，最后输出对于每一个

a_i

，至少经过几次修改能使

a_i\ge P

。

思路：

性质 1：或运算能让原来的数变大或不变，肯定不会变小。

对于或运算

a|b

的对于每一位而言，如果同为 0 则结果为 0，其中一个为 1 则结果为 1，同为 1 则结果为 1。所以我们可以得出结论

a\,|\,b\ge \operatorname{max(a,b)}

。

性质 2：或运算具有结合律。

与性质 1 类似地，我们很容易推出或运算

a \,| \, b\,|\, c=a\,|\,(\,b\,|\,c\,)

。

结合以上两种性质，我们有以下思考：

可以使用线段树维护或运算的信息。线段树是通过预处理 $O(n)$ 个均匀的区间以达到 $O(\log n\cdot f(n))$ 处理一次半群信息的修改或查询的数据结构。

半群：定义集合

S

和二元运算

\star

(S,\star)

。

A,B\in S

，

A\star B \in S

有封闭性。

(A\star B)\star C = A\star (B \star C)

有结合律。

f(n)

：

\star

满足上述条件的

f(n)

均可。

由性质 2 得出或运算具有结合律，在这里我们就可以用线段树维护区间的运算信息，每个节点的值

tree[x]=tree[lson] \,| \,tree[rson]

。

CPP

void pushup(int x){
    tree[x]=tree[lx]|tree[rx];//类似区间加，因为或运算同样具有结合律
}

由性质 1 得知每一个 $a_i$ 的增长是有单调性的，那么我们就可以考虑使用二分法。比较特殊的是这里是带有区间修改的。我们可以二分答案每一个 $a_i$ 的修改次数，若 $a_i \ge P$ ,那么我们就减少修改次数，否则增加修改次数，最后我们就能二分出使每一个 $a_i \ge P$ 的最少修改次数。恰好的是，线段树本身是一个满二叉树，这很适合我们进行二分操作。

接下来该处理修改的问题了。输出答案时我们只需要在线段树上二分答案，所以修改区间的问题就转化为了修改线段树上 $[L,R]$ 的或值。对于与每一个 $a_i$ ,我们只考虑影响到第 $i$ 位的修改。然而对于位置 $i$ ,可能会被区间多次覆盖，换句话说就是可能会被修改多次。这里有一个妙用：邻接表！！！ 我们在询问第 $L$ 个元素 $a_L$ 的答案时，先把以修改区间为 $[L,R]$ 的操作加入线段树中，这样对于 $a_{[L,R]}$ ，每一个 $a_i$ 在进行二分答案时都会被该次操作影响。而在询问第 $R+1$ 个元素 $a_{R+1}$ 时，是不会受本次操作影响的。所以要把线段树上该次操作所在节点的值设为 $0$ ，这样二分时就不会受影响了。

CPP

int head[N];
struct Edge{
    int nex,val,pos;
//nex:以head[i]为首的下一次修改
//val:本次修改的值
//pos:本次修改的位置
}edge[N<<1];//2倍空间，因为每次修改要加两次边
void addedge(int u,int pos,int xnum){
    edge[++cnt].val=xnum;
    edge[cnt].nex=head[u];
    edge[cnt].pos=pos;
    head[u]=cnt;
}//朴素邻接表
int main(){
    for(int i=1;i<=q;i++){
        int x,l,r;
        scanf("%d%d%d",&l,&r,&x);
        addedge(l,i,x);
        //给 l 的位置加上本次修改的值，这个操作会影响后面所有的二分答案
        addedge(r+1,i,0);
        //给r+1的位置撤销本次修改的操作，使区间 [R,n] 不受该次修改的影响。
    }
}

继续第二点的思路，我们就可以把第 $i$ 次修改放在编号为 $i$ 的叶子节点上，然后 pushup() 上传，就得到了原始的 $a_i$ 经过 $[L,R]$ 次修改后的结果。

CPP

void update(int x,int l,int r,int pos,int val){
    //找到位置为pos的叶子节点并修改要或的值为val
    if(l==r){//叶子
        tree[x]=val;return;
        //将叶子节点的值设为本次修改或的值val
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(lx,l,mid,pos,val);
    else update(rx,mid+1,r,pos,val);
    //递归左子树或右子树找到位置为pos的叶子节点并修改
    pushup(x);//记得上传标记方便区间访问
}

剩下的就是线段树二分的部分。这里有一个很巧妙的点，可以看到主函数中，如果碰到了需要修改的地方，再用 update() 修改线段树。代码中的注释已经足够详细。

CPP

int ask(int x,int l,int r,int num){
//询问a[i]即num，至少经过多少次修改能>=P
    if(l==r){//叶子
        if((num|tree[x])<p) return -1;
        //尽力了尽力了，到达叶子节点还无法战胜
        return l;//找到了使ai>=P的最小值l，即该次修改的位置/编号
    }
    int mid=(l+r)>>1;
    if((tree[lx]|num)>p) return ask(lx,l,mid,num);
    //若左子树的或值已经能满足，那就递归左子树
    else return ask(rx,mid+1,r,num|tree[lx]);
    //左子树满足不了，到右子树找
    //注意这里传入num|tree[lx],已经或上了左子树所有或值
    //类比第k小数传入k-tree[lx].siz
}
int main(){
    for(int i=1;i<=n;i++){
      for(int j=head[i];j;j=edge[j].nex)  update(1,1,q,edge[j].pos,edge[j].val);
        printf("%d ",ask(1,1,q,a[i]));
    }
}

最后附上完整代码

CPP

#include<bits/stdc++.h>
#define N 1000001
#define ll long long
#define lx x<<1
#define rx x<<1|1
using namespace std;
int n,p,q,cnt;
int a[N];
int head[N];
ll tree[N<<2];
struct Edge{
    int nex,val,pos;
}edge[N<<1];
void addedge(int u,int pos,int xnum){
    edge[++cnt].val=xnum;
    edge[cnt].nex=head[u];
    edge[cnt].pos=pos;
    head[u]=cnt;
}
void pushup(int x){
    tree[x]=tree[lx]|tree[rx];//类似区间加，因为或运算同样具有结合律
}
void update(int x,int l,int r,int pos,int val){
    if(l==r){
        tree[x]=val;return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(lx,l,mid,pos,val);
    else update(rx,mid+1,r,pos,val);
    pushup(x);
}
int ask(int x,int l,int r,int num){
    if(l==r){
        if((num|tree[x])<p) return -1;
        return l;
    }
    int mid=(l+r)>>1;
    if((tree[lx]|num)>p) return ask(lx,l,mid,num);
    else return ask(rx,mid+1,r,num|tree[lx]);
}
int main(){
    //freopen("8955.in","r",stdin);
    cin>>n>>q>>p;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=q;i++){
        int x,l,r;
        scanf("%d%d%d",&l,&r,&x);
        addedge(l,i,x);
        addedge(r+1,i,0);
    }
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=edge[j].nex) update(1,1,q,edge[j].pos,edge[j].val);
        printf("%d ",ask(1,1,q,a[i]));
    }
    return 0;
}

题解：P8955 「VUSC」Card Tricks

文章操作