#與或
描述

樣例輸入
5 8
1 3 2 5 4
3 1 3
2 1 1 5
3 1 3
1 1 4 6
2 3 4 1
3 2 3
2 2 3 4
3 1 5
**樣例輸出 **
3
5
3
7
提示
對于30%數據，N,Q<=2000
另有30%數據，第三類操作L==R
對于100%數據，N,Q<=200000，Ai∈[ 0 , 2^20 )

線段樹基礎操作，本蒟蒻由大佬科普過兩種做法，但總體思路都是一致的，首先我們需要明確|操作和&操作分別的作用是什么，

|操作，即按位或操作，對于兩個進行按位或操作的二進制數的同一位，只要其中一個為$1$，那么答案的這一位就為$1$。

&操作，即按位與操作，對于兩個進行按位與操作的二進制數的同一位，只要其中一個為$0$，那么答案的這一位就為$0$。

我們總結一下兩種操作的作用吧，如果使用按位與來進行修改，那么如果$x$的第$i$位是$0$，那么答案的第$i$位也被強制成了$0$，同理，如果使用按位或來進行修改，那么如果$x$的第$i$位是$1$，那么答案的第$i$位也被強制成了$1$，也就是說，每次操作之后，都有一段區間中的數的某些二進制位被修改成了相同的，而整個序列中相同的二進制位數隨著修改次數的增多顯然是單調不降的，這樣的話，由于每個數最多有$20$位，所以即使我們使用帶有暴力思想的線段樹也是可以$A$掉這題的。具體怎么實現呢？由于使整個區間二進制位相同的修改次數有了保障，我們不妨直接在修改當前線段樹節點的判斷條件上做做文章，我們知道原本修改當前線段樹節點的判斷條件是$(ql\le T[p].l$ $and$ $T[p].r\le qr),$我們如果再增加一個限制條件$T[p].minn==T[p].maxn$，經過驗證同樣可以過掉隨機數據。

---

先來一波假算法卡隨機數據的（某學長的）代碼：

#include<bits/stdc++.h> using namespace std; const int N=2e5+5,MAX=(1<<20)-1; int read(){int res=0,f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) res=(res<<1)+(res<<3)+(c^'0');return res*f; } int n,a[N],Q; struct node{int ls,rs;int max,min,S;int tag;node(){ls=rs=max=S=0;tag=-1;} }tr[N<<1]; int rt=0,node=0; #define gm int mid=s+t>>1; int &l(int x){return tr[x].ls;} int &r(int x){return tr[x].rs;} void set_or(int x,int s){tr[x].max|=s;tr[x].min|=s;tr[x].tag=tr[x].max; } void set_and(int x,int s){tr[x].max&=s;tr[x].min&=s;tr[x].tag=tr[x].max; } void down(int x){if(tr[x].tag!=-1){tr[l(x)].max=tr[r(x)].max=tr[l(x)].min=tr[r(x)].min=tr[l(x)].tag=tr[r(x)].tag=tr[x].tag;tr[x].tag=-1;} } void up(int x){tr[x].max=max(tr[l(x)].max,tr[r(x)].max);tr[x].min=min(tr[l(x)].min,tr[r(x)].min); } void build(int &x,int s=1,int t=n){x=++node;if(s==t){tr[x].max=tr[x].min=a[s];return;}gm;build(l(x),s,mid);build(r(x),mid+1,t);up(x); } void Or(int x,int v,int qs,int qt,int s,int t){if(qs<=s&&t<=qt&&tr[x].max==tr[x].min){set_or(x,v);return;}gm;down(x);if(qs<=mid) Or(l(x),v,qs,qt,s,mid);if(qt >mid) Or(r(x),v,qs,qt,mid+1,t);up(x); } void And(int x,int v,int qs,int qt,int s,int t){if(qs<=s&&t<=qt&&tr[x].max==tr[x].min){set_and(x,v);return;}gm;down(x);if(qs<=mid) And(l(x),v,qs,qt,s,mid);if(qt >mid) And(r(x),v,qs,qt,mid+1,t);up(x); } int que(int x,int qs,int qt,int s,int t){if(qs<=s&&t<=qt) return tr[x].max;gm;down(x);int res=0;if(qs<=mid) res=max(res,que(l(x),qs,qt,s,mid));if(qt >mid) res=max(res,que(r(x),qs,qt,mid+1,t));return res; } int main(){n=read();Q=read();for(int i=1;i<=n;++i) a[i]=read();build(rt,1,n);for(int i=1,opt,l,r,x;i<=Q;++i){opt=read();l=read();r=read();if(opt==1){x=read();And(rt,x,l,r,1,n);}else if(opt==2){x=read();Or(rt,x,l,r,1,n);}else{cout << que(rt,l,r,1,n) << '\n';}}return 0; }

---

然后我們繼續思考這道題的正解吧，由于這道題的按位與和按位或操作只會使整個區間的某幾位發生強制的變化，所以如果整個修改區間的那幾位都是相同的話，這次修改并不影響修改區間的大小順序，因為每個數相當于都強制變化了同樣的值，因此在維護區間最大值的同時，我們同時維護一個叫做$T[p].same$的的二進制數來表示當前區間從第一個二進制位到最后的二進制位的異同性。顯然我們可以假設整個區間的第$i$位都相同時$same$的第$i$位為$1$,否則為$0$，這時新問題出現了，如何區間合并$same$的值呢？，我們應該這樣思考，如果左右兒子的$same$在第$i$位上有至少一個為$0$，那么說明整個區間一定有不同的第$i$位，然后$T[p].same$顯然就為$0$，如果左右兒子的$same$值都為$1$的話，說明左右子區間的數的第$i$位都分別相同，我們再用兩個子區間的$maxn$值篩選出整個區間都有可能相同的二進制位，最后再與左右區間的$same$比較一下即可合并了，也就是說$T[p].same=(T[lc].same$ $and$ $T[rc].same)$ $and$ $((T[lc].maxn$ $xor$ $ T[rc].maxn))$,在我們能夠維護出$sameKaTeX parse error: Expected 'EOF', got '&' at position 10: 的值過后，對于|（&?）操作我們只需在判斷是否修改當…check$函數的判斷就行了，具體方式可以參考本蒟蒻的代碼。

然后說說實現該算法的兩種思想：

---

第一種：寫兩個$update$函數打區間標記分別對操作$1,2$進行修改，本蒟蒻調了很久。相比第二種來說思維難度較低，代碼有對稱性，但容易滑稽。

代碼如下：

#include<bits/stdc++.h> #define N 200005 #define lc (p<<1) #define rc (p<<1|1) #define mid (T[p].l+T[p].r>>1) #define inf ((1<<20)-1) using namespace std; struct Node{int l,r,sm,mx,lz1,lz2; }T[N<<2]; int a[N],n,q; inline void pushup(int p){T[p].mx=max(T[lc].mx,T[rc].mx);T[p].sm=(T[lc].sm&T[rc].sm)&(~(T[lc].mx^T[rc].mx)); } inline void pushnow(int p,int sm,int mx){T[p].sm|=sm;T[p].mx=(T[p].mx&(~sm))|(mx&sm); } inline void pushdown(int p){if(T[p].l==T[p].r)return;pushnow(lc,T[p].sm,T[p].mx);pushnow(rc,T[p].sm,T[p].mx); } inline void build(int p,int l,int r){T[p].l=l,T[p].r=r,T[p].lz1=T[p].lz2=0;if(l==r){T[p].mx=a[l],T[p].sm=inf;return;}build(lc,l,mid);build(rc,mid+1,r);pushup(p); } inline bool check1(int p,int v){return ((inf^v)&T[p].sm)==(inf^v);} inline bool check2(int p,int v){return (T[p].sm&v)==v;} inline void update1(int p,int ql,int qr,int v){pushdown(p);if(ql>T[p].r||qr<T[p].l)return;if(ql<=T[p].l&&T[p].r<=qr){if(T[p].l==T[p].r||check1(p,v)){T[p].mx&=v; return;}}if(qr<=mid)update1(lc,ql,qr,v);else if(ql>mid)update1(rc,ql,qr,v);else update1(lc,ql,mid,v),update1(rc,mid+1,qr,v);pushup(p); } inline void update2(int p,int ql,int qr,int v){pushdown(p);if(ql>T[p].r||qr<T[p].l)return;if(ql<=T[p].l&&T[p].r<=qr){if(T[p].l==T[p].r||check2(p,v)){T[p].mx|=v; return;}}if(qr<=mid)update2(lc,ql,qr,v);else if(ql>mid)update2(rc,ql,qr,v);else update2(lc,ql,mid,v),update2(rc,mid+1,qr,v);pushup(p); } inline int query(int p,int ql,int qr){pushdown(p);if(ql>T[p].r||qr<T[p].l)return 0;if(ql<=T[p].l&&T[p].r<=qr)return T[p].mx;if(qr<=mid)return query(lc,ql,qr);if(ql>mid)return query(rc,ql,qr);return max(query(lc,ql,mid),query(rc,mid+1,qr)); } int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;++i)scanf("%d",&a[i]);build(1,1,n);while(q--){int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op==3){printf("%d\n",query(1,l,r));continue;}int v;scanf("%d",&v);if(op==1)update1(1,l,r,v);else update2(1,l,r,v);}return 0; }

---

第二種：我們利用位運算將按位與的修改轉化成為按位或的修改，實現難度較低，但思維要求比較高，請各位大佬務必照著代碼中的轉化方式自己手推一遍，加深理解。

代碼如下：

#include<bits/stdc++.h> #define inf (1<<20)-1 #define lc (p<<1) #define rc (p<<1|1) #define mid (T[p].l+T[p].r>>1) #define N 200005 using namespace std; int n,q,a[N]; struct Node{int l,r,sm,mx;}T[N<<2]; inline void pushnow(int p,int sm,int mx){T[p].sm|=sm;T[p].mx=(T[p].mx&(~sm))|(mx&sm); } inline void pushdown(int p){pushnow(lc,T[p].sm,T[p].mx);pushnow(rc,T[p].sm,T[p].mx); } inline void pushup(int p){T[p].sm=(~(T[lc].mx^T[rc].mx))&(T[lc].sm&T[rc].sm);T[p].mx=max(T[lc].mx,T[rc].mx); } inline void build(int p,int l,int r){T[p].l=l,T[p].r=r;if(l==r){T[p].sm=inf,T[p].mx=a[l];return;}build(lc,l,mid);build(rc,mid+1,r);pushup(p); } inline int query(int p,int ql,int qr){if(qr<T[p].l||T[p].r<ql)return 0;if(ql<=T[p].l&&T[p].r<=qr)return T[p].mx;pushdown(p);return max(query(lc,ql,qr),query(rc,ql,qr)); } inline void update(int p,int ql,int qr,int sm,int v){if(qr<T[p].l||T[p].r<ql)return;if(ql<=T[p].l&&T[p].r<=qr){if(T[p].l==T[p].r||((sm&T[p].sm)==sm)){T[p].mx=(T[p].mx&(~sm))|(v&sm);return;}}pushdown(p);update(lc,ql,qr,sm,v);update(rc,ql,qr,sm,v);pushup(p); }int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;++i)scanf("%d",&a[i]);build(1,1,n);while(q--){int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op==1){int v;scanf("%d",&v);update(1,l,r,inf^v,0);}if(op==2){int v;scanf("%d",&v);update(1,l,r,v,v);}if(op==3)printf("%d\n",query(1,l,r));}return 0; }

這道題加強了本蒟蒻對線段樹（二進制）的理解，畢竟調了一個下午加一個晚上。

轉載于:https://www.cnblogs.com/ldxcaicai/p/9738560.html

總結

以上是生活随笔為你收集整理的2018.06.28 与或（线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。