Description

Kaiser终于成为冒险协会的一员,这次冒险协会派他去冒险,他来到一处古墓,却被大门上的守护神挡住了去路,守护神给出了一个问题,

只有答对了问题才能进入,守护神给出了一个自然数序列a,每次有一下三种操作。

1,给出l,r,x,将序列l,r之间的所有数都 and x

2,给出l,r,x,将序列l,r之间的所有数都 or x

3,给出l,r,询问l,r之间的最大值

Input

第一行包含两个整数 n,m 接下来一行包含 n 个整数, 表示a序列,接下来 m 行, 每行描述了一个操作.

2<=n<=2e5 2<=q<=2e5,0<=ai<=2^20.

Output

对于每个第三类询问, 输出一个数字.

Sample Input

3 5

9 19 0

3 2 3

2 3 3 18

1 2 2 10

3 1 2

1 1 3 11

Sample Output

19

9


看到题目的时候相当僵硬,然后YY了一个算法然后僵硬了几个小时最后GG,我自己的错误算法还是不在这里说了。。说多了都是泪

重大更新,我的代码终于调出来了,比正解更好理解!!!在正解后给予解释!!!!

正解如下:

首先我们可以发现,与和或的操作一个是有0变成0,一个是有1变成1

那么如果一个数与、或上另一个数vl,只跟另一个数的二进制位上为0、1的位有关

我们考虑在什么情境之下我们可以通过更新的vl值获得我们需要的最大值maxn,既然是区间操作,我们不难想到用线段树进行求解,但是单单是vl,我们并不能得到想要的maxn,所以我们需要维护其他的辅助变量

我们发现&和|操作所关联的二进制位只有vl上的0或者1,所以我们可以考虑定义线段树上区间的sam,如果一个区间的所有数在第i个二进制位上的数码相等,sam的这个二进制位上的数为1,否则为0

通过更新sam,我们是可以很方便的计算和更新maxn的

但是当一个区间存在多个不同的sam怎么办?我们用vl值进行更新的时候依然不能很方便的进行计算,所以我们定义check函数来限制线段树修改的边界问题,显然,当满足所有(&vl且vl上为0的位sam上为1)或者(|vl且vl上为1的位sam上为1)我们只需要用vl&、|上当前区间最大值就好,不满足就向下递归问题

现在我们考虑向上维护sam值,显然,对于一个二进制位,只有当左右两区间的sam在这个二进制上的值都为1且左右两区间的数在这两个二进制位上相等才行,可以表示成sam[t]=(sam[LD] & sam[RD]) & (INF ^ maxn[LD] ^ maxn[RD]),这里INF定义为二进制上的极大值((1<<20)-1),然后maxn直接左右区间选择max就好了

那么如何向下更新呢?正解的思路真的比较神奇

我们把|操作强行通过某种等价的方式转化成&操作,然后只用一个修改函数进行修改,这个有兴趣的照着代码枚举二进制情境验证一下吧。

其次,还有一个比较玄学的是正解没有加lazy标记,直接用父亲节点t的maxn和sam值对儿子节点s的maxn和sam值进行更新,这个稍微讲一下,因为所有在sam[t]上出现的1一定会在sam[s]上出现,所以sam[s]|=sam[t]就可以维护,然后对于maxn,我们先把maxn[s]上左右和sam[t]有关的二进制位全部变成零,然后再或上sam[t]和maxn[t]均为1的二进制就好了


#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define INF ((1<<20)-1)
#define LD (t<<1)
#define RD ((t<<1)|1)
struct Segment_Tree{
//1->& 2->|
int num[N],l[N<<2],r[N<<2];
int maxn[N<<2],sam[N<<2];
void pushup(int t){
sam[t]=(sam[LD]&sam[RD])&(INF^(maxn[LD]^maxn[RD]));
maxn[t]=max(maxn[LD],maxn[RD]);
}
void pushnow(int t,int v1,int v2){
sam[t]|=v1;
maxn[t]=(maxn[t]&(INF^v1))|(v1&v2);
}
void pushdown(int t){
pushnow(LD,sam[t],maxn[t]);
pushnow(RD,sam[t],maxn[t]);
}
void build(int t,int ll,int rr){
if(ll>rr)return;
l[t]=ll;r[t]=rr;
if(ll==rr){
maxn[t]=num[ll];
sam[t]=INF;
return;
}
int mid=(ll+rr)>>1;
build(LD,ll,mid);
build(RD,mid+1,rr);
pushup(t);
}
void modify(int t,int ll,int rr,int v1,int v2){
if(l[t]>rr||r[t]<ll)return;
if(ll<=l[t]&&r[t]<=rr){
if(l[t]==r[t]||((v1&sam[t])==v1)){
maxn[t]=(maxn[t]&(INF^v1))|(v1&v2);
return;
}
}
pushdown(t);
modify(LD,ll,rr,v1,v2);
modify(RD,ll,rr,v1,v2);
pushup(t);
}
int query(int t,int ll,int rr){
if(l[t]>rr||r[t]<ll)return 0;
if(ll<=l[t]&&r[t]<=rr)return maxn[t];
pushdown(t);
return max(query(LD,ll,rr),query(RD,ll,rr));
}
}tree;
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&tree.num[i]);
tree.build(1,1,n);
for(int i=1;i<=m;i++){
int op,l,r,vl;
scanf("%d%d%d",&op,&l,&r);
if(op==1){
scanf("%d",&vl);
tree.modify(1,l,r,vl^INF,0);
}else if(op==2){
scanf("%d",&vl);
tree.modify(1,l,r,vl,vl);
}else printf("%d\n",tree.query(1,l,r));
}
return 0;
}

更新:

身为一个不顾一切强行刚的OIER,我肯定是会刚题刚到凌晨的,然后我就把它刚出来了,我的做法将&和|的操作分别进行,在modify过程中肯定是很好理解的,现在解释一下对&和|的边界设定:

定义check1检查对&的modify:{

我们发现当vl涉及的数码为0的所有二进制位在取件sam中都为1的时候,那么vl对于区间中的所有二进制的这几位的影响相同,不会改变大小顺序,所以可以直接进行maxn的更新,条件:((INF ^ vl)&sam[t]) == (INF^vl)

}

定义check2检查对|的modify:{

我们发现当vl涉及的数码为1的所有二进制位在取件sam中都为1的时候,那么vl对于区间中的所有二进制的这几位的影响相同,不会改变大小顺序,所以可以直接进行maxn的更新,条件:(vl&sam[t]) == vl

}

然后注意这个时候需要在pushdown的时候进行边界条件判定,不然会出现奇奇怪怪的错误

附上代码:

#include<bits/stdc++.h>
using namespace std;
#define INF ((1<<20)-1)
#define N 200010
#define LD (t<<1)
#define RD ((t<<1)|1)
struct Segment_Tree{
//1->& 2->|
int num[N],sam[N<<2],maxn[N<<2],l[N<<2],r[N<<2];
void pushup(int t){
sam[t]=(sam[LD]&sam[RD])&(INF^(maxn[LD]^maxn[RD]));
maxn[t]=max(maxn[LD],maxn[RD]);
}
void pushnow(int t,int v1,int v2){
sam[t]|=v1;
maxn[t]=(maxn[t]&(INF^v1))|(v1&v2);
}
void pushdown(int t){
if(l[t]==r[t])return;
pushnow(LD,sam[t],maxn[t]);
pushnow(RD,sam[t],maxn[t]);
}
void build(int t,int ll,int rr){
if(ll>rr)return;
l[t]=ll;r[t]=rr;
if(ll==rr){sam[t]=INF;maxn[t]=num[ll];return;}
int mid=(ll+rr)>>1;
build(LD,ll,mid);
build(RD,mid+1,rr);
pushup(t);
}
bool check1(int t,int vl){return ((INF^vl)&sam[t])==(INF^vl);}
bool check2(int t,int vl){return (vl&sam[t])==vl;}
void modify1(int t,int ql,int qr,int vl){
if(r[t]<ql||qr<l[t])return;
pushdown(t);
if(ql<=l[t]&&r[t]<=qr)
if(l[t]==r[t]||check1(t,vl)){maxn[t]&=vl;return;}
modify1(LD,ql,qr,vl);
modify1(RD,ql,qr,vl);
pushup(t);
}
void modify2(int t,int ql,int qr,int vl){
if(r[t]<ql||qr<l[t])return;
pushdown(t);
if(ql<=l[t]&&r[t]<=qr)
if(l[t]==r[t]||check2(t,vl)){maxn[t]|=vl;return;}
modify2(LD,ql,qr,vl);
modify2(RD,ql,qr,vl);
pushup(t);
}
int query(int t,int ql,int qr){
if(r[t]<ql||qr<l[t])return 0;
if(ql<=l[t]&&r[t]<=qr)return maxn[t];
pushdown(t);
return max(query(LD,ql,qr),query(RD,ql,qr));
}
}tree;
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&tree.num[i]);
tree.build(1,1,n);
for(int i=1;i<=m;i++){
int op,l,r,vl;
scanf("%d%d%d",&op,&l,&r);
if(op==1){
scanf("%d",&vl);
tree.modify1(1,l,r,vl);
}else if(op==2){
scanf("%d",&vl);
tree.modify2(1,l,r,vl);
}else printf("%d\n",tree.query(1,l,r));
}
return 0;
}
04-25 07:19