CSA70- And or Max
なんか書きます
遅延セグ木を書きます。各ノードごとに、次の情報を持ちます。
ma → その区間のmax
same → その区間のi桁目がすべて同じだったら、sameのi桁目は1、そうでないならsameのi桁目は0。
por → porのi桁目は、その区間に一様にi桁目を1にするorが飛んできたかどうか(遅延させておくための変数)
pand →pandのi桁目は、その区間に一様にi桁目を0にするandが飛んできたかどうか
例えば、長さ4の区間 {01, 11, 11 , 01}に、一様に and 01したとします。
このとき、same=01 (右のほうの桁はすべて同じなので)
por = 00 (orクエリ飛んできてないので)
pand = 10 (左の桁をすべて0にするようなandクエリが飛んできてるので)
という感じです。
これらの情報を必死に維持しながら遅延セグ木を営むのですが、maとかsameの更新で困ってしまうと思います(porとpandの伝搬は気合でやるとふつうにできます)
更新で困ってしまう時とは、どのようなときでしょうか?
それは、sameが0となっているような桁において、porやpandが1となるケースです(sameが1になっていれば、普通にできますよね)
このときはどうするかというと、とりあえずporやpandの情報だけ伝搬したあとに、2つの子ノードについて再帰的に計算させます
ここまで読んだ限りだと、O(N^2)ではと思うかもしれません。しかし、ならし解析を用いると、実はO*1です
ちなみに、下の子の情報からsameを再計算するときは、
same[k]=same[k*2+1]&same[k*2+2]&(ma[k*2+1]^ma[k*2+2]^mask)、とします。(maskは、すべての桁が1であるようなやつ)(mask=2^20 -1)
2つの子のどちらかでsameが0になっているような桁は、0になるべきです。
また、2つの子のどちらにおいてもsameのi桁目が1になっていたとしても、左の子ではすべて0、右の子ではすべて1、みたいなケースもあるので、そのようなケースを右辺の一番右の項によって潰します。
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} constexpr int SEG=1<<18; constexpr int mask=(1<<20)-1; int same[SEG*2]; int por[SEG*2],pand[SEG*2]; int ma[SEG*2]; int N,Q; int A[SEG]; void build(int k=0,int l=0,int r=SEG){ if(l+1==r){ same[k]=mask; ma[k]=A[l]; return; } build(k*2+1,l,(l+r)/2); build(k*2+2,(l+r)/2,r); same[k]=same[k*2+1]&same[k*2+2]&(ma[k*2+1]^ma[k*2+2]^mask); ma[k]=max(ma[k*2+1],ma[k*2+2]); } void push(int k){ if(k<SEG-1){ por[k*2+1]|=por[k]; por[k*2+1]&=mask^pand[k]; pand[k*2+1]|=pand[k]; pand[k*2+1]&=mask^por[k]; por[k*2+2]|=por[k]; por[k*2+2]&=mask^pand[k]; pand[k*2+2]|=pand[k]; pand[k*2+2]&=mask^por[k]; } if((same[k]&por[k])!=por[k]||(same[k]&pand[k])!=pand[k]){ push(k*2+1); push(k*2+2); same[k]=same[k*2+1]&same[k*2+2]&(ma[k*2+1]^ma[k*2+2]^mask); ma[k]=max(ma[k*2+1],ma[k*2+2]); } else{ ma[k]|=por[k]; ma[k]&=mask^pand[k]; } por[k]=pand[k]=0; } void update(int a,int b,int t,int x,int k=0,int l=0,int r=SEG){ push(k); if(r<=a||b<=l)return; if(a<=l&&r<=b){ if(t==0)pand[k]=mask^x; else por[k]=x; push(k); return; } update(a,b,t,x,k*2+1,l,(l+r)/2); update(a,b,t,x,k*2+2,(l+r)/2,r); ma[k]=max(ma[k*2+1],ma[k*2+2]); same[k]=same[k*2+1]&same[k*2+2]&(ma[k*2+1]^ma[k*2+2]^mask); } int query(int a,int b,int k=0,int l=0,int r=SEG){ push(k); if(r<=a||b<=l)return 0; if(a<=l&&r<=b)return ma[k]; return max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r)); } signed main(){ scanf("%lld%lld",&N,&Q); rep(i,N)scanf("%lld",&A[i]); build(); while(Q--){ int t,l,r,x; scanf("%lld%lld%lld",&t,&l,&r); t--;l--; if(t!=2){ scanf("%lld",&x); update(l,r,t,x); } else{ printf("%lld\n",query(l,r)); } } return 0; }
*1:N+Q) logNlogA)とかであることがわかります(Aは、数列の最大値) 再計算が走ったノードは、sameの立っている1の数が厳密に増えます。そして、sameのすべての桁が1となっていれば再計算はまったく走りません。 sameの立っている1の数が減るのは、とうぜんandやorのクエリのときですが、このときsameが荒らされるノードの数はO(logN)個です(いつものセグ木の再帰でたどる頂点のみ) これらの各ノードの、すべての桁が荒らされたとしても、一度のクエリで荒らされる桁の数はO(logN logA)であることが分かります。 したがって、どこかのsameのどこかの桁が1→0となる回数はO(Q logNlogA)回程度であるわけです。したがって、再計算が走る回数はO(NlogA+ QlogNlogA)です。(NlogAは、もともとsameが0になっている場所の分) 再計算以外の動作は遅延セグ木そのままですから、O(N+QlogN+NlogA+QlogNlogA)=O((N+QlogN) logA