らての精進日記

修行をします

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