题解：P8955 「VUSC」Card Tricks
BestCNSoda
·
·
题解
给刚学整体二分的 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\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];//类似区间加，因为或运算同样具有结合律
}
```
2. 由*性质 1* 得知每一个 $a_i$ 的增长是有单调性的，那么我们就可以考虑使用**二分法**。比较特殊的是这里是带有区间修改的。我们可以二分答案每一个 $a_i$ 的修改次数，若 $a_i \ge P$,那么我们就减少修改次数，否则增加修改次数，最后我们就能二分出**使每一个 $a_i \ge P$ 的最少修改次数**。恰好的是，线段树本身是一个满二叉树，这很适合我们进行二分操作。
----------------------------------
3. 接下来该处理修改的问题了。输出答案时我们只需要在线段树上二分答案，所以修改区间的问题就转化为了修改线段树上 $[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] 不受该次修改的影响。
}
}
```
---------------
4. 继续第二点的思路，我们就可以把第 $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);//记得上传标记方便区间访问
}
```
------------------------------
5. 剩下的就是线段树二分的部分。这里有一个很巧妙的点，可以看到主函数中，如果碰到了需要修改的地方，再用 `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;
}
```