問題

Problem - F - Codeforces

問題概要

はじめ、長さ $n$ の数列 $a$ と整数 $x$ が与えられる。次のようなクエリを考える：

クエリ1 $(i,y)$ : $a_i$ を $y$ に変更する。
クエリ2 $(l,r)$ : $l \le L \le R \le r$ を満たすpair $(L,R)$ について、数列 $a$ における区間 $[L,R]$ のすべての要素のbitwise ORを取ったときの値が $x$ 以上になるようににできるpair $(L,R)$ の個数がいくつあるかを答える。

クエリ1と2が合計で $m$ 個与えられるので、順に処理せよ。

$1 \le n \le 10^5$
$1 \le m \le 10^5$
$0 \le a_i , x \lt 2^{20}$

アイデア

区間のvalueをその区間全体に対してbitwise ORを取ったときの値とし、「良い区間」というのを、その区間の全体のbitwise ORを取ったときに、 $x$ が部分として含まれているときにその区間が良い区間であると呼ぶことにする。

クエリ2についてどう高速に答えるかを考えたいが、その前に、まずはクエリ2に $[ 1 , n ]$ が来た場合にどうするかを考える。

分割統治のアプローチを考えてみる。区間を、 $[ 1 , \frac{n}{2} ]$ と $[ \frac{n}{2} +1 , n ]$ に分割し、それぞれの区間内で完結するものについては再帰的にそちらで計算してもらうことにして、ここでは、区間の左端が前者にあり、右端が後者にあるものの中で、条件を満たしている区間が何個あるかを数えたい。

さて、区間の左端のindex $i$ に対して、区間 $[ i, \frac{n}{2} ]$ (いわゆるsuffix)のvalueを考えてみると、 $i$ が減っていくに従って立つビットの個数は単調増加になっているはずで、立ったビットが戻ることもないので、この $\frac{n}{2}$ 個の区間のvalueについて、現れる値の種類数は $log( MAX a_i)$ 個しか無いということが分かる。

ということで、区間のマージを考えるときには、左側に関してはsuffix(各ビットごとに、現れてくる最も右の位置)が欲しくて、右側に関してはprefix(各ビットごとに。現れてくる最も左の位置)が欲しくなる。左側は $i$ を減らす方向に動かすと考えると、右側も同様に、prefixを全部含んでいる状態からスタートして徐々に左に動いていく、みたいな感じで尺取りっぽくやれば区間をまたぐ良い区間の個数が $O(log( MAX a_i))$ で数えることができる。

以上で考えていたことをそのままSegment Treeに乗せて処理することを考える。セグ木の1つのノードに乗せる必要があるものは、上でも述べたようにsuffixの情報とprefixの情報、あとは区間内で完結している答えの個数、の3つの情報である。上でも考察したように、このセグ木のノードとノードのmergeが $O(log( MAX a_i))$ で実現できることが分かっている。つまり、クエリ2に対して $O(logn \ * \ log( MAX a_i))$ で答えることができる、ということである。

では、残ったupdateに関してだが、点更新によって、ノードの更新をしなきゃいけない区間の個数というのは、セグ木の深さを考えると $O(logn)$ 個なので、updateクエリも $O(logn \ * \ log( MAX a_i))$ で実現できる。

以上より、全体の計算量は $O( (n+m) \ * logn \ * \ log( MAX a_i))$ となり、間に合う。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

using pi = pair<int,int>;

const int INF = 19191919;
const int B = 20;

int x;

struct Seg{
    // [l,r)
    int l,r;
    int rpos[B],lpos[B];
    ll val;

    Seg(){
        l=-1;
        r=-1;
        fill(lpos,lpos+B,INF);
        fill(rpos,rpos+B,-INF);
        val = 0;
    }
    Seg(int idx, int s){
        l = idx;
        r = idx+1;
        val = (s>=x);

        fill(lpos,lpos+B,INF);
        fill(rpos,rpos+B,-INF);
        rep(i,B){
            if(s>>i&1){
                lpos[i] = min(lpos[i], idx);
                rpos[i] = max(rpos[i], idx);
            }
        }
    }
};

void merge(Seg &ret, const Seg &L, const Seg &R){
    if(L.l==-1){
        ret = R;
        return;
    }
    if(R.l==-1){
        ret = L;
        return;
    }

    ret.l = L.l;
    ret.r = R.r;

    rep(i,B){
        ret.lpos[i] = min(L.lpos[i], R.lpos[i]);
        ret.rpos[i] = max(L.rpos[i], R.rpos[i]);
    }

    // calc val
    ret.val = L.val+R.val;

    // L.rpos と R.lposに注目
    pi pl[B],pr[B+1];
    rep(i,B){
        pl[i] = {L.rpos[i],i};
        pr[i] = {R.lpos[i],i};
    }
    pr[B] = {R.l,-1};
    sort(pl,pl+B, greater<pi>());
    sort(pr,pr+B+1, greater<pi>());

    int rmask = (1<<B)-1, lmask = 0;
    int lidx = 0;
    rep(i,B+1){
        int b = pr[i].se;
        int Rlen = 0;
        if(i==0 || pr[i-1].fi==INF) Rlen = R.r-1 - pr[i].fi + 1;
        else Rlen = pr[i-1].fi-1 - pr[i].fi + 1;
        Rlen = max(Rlen,0);

        while(lidx<B && (rmask|lmask)<x){
            lmask |= (1<<pl[lidx].se);
            ++lidx;
        }

        int Llen = 0;
        if(lidx==0) Llen = L.r-1-L.l+1;
        else Llen = pl[lidx-1].fi-L.l+1;
        Llen = max(Llen,0);

        if((rmask|lmask)>=x) ret.val += (ll)Rlen*Llen;
        if(b>=0) rmask ^= (1<<b);
    }
}

struct SegTree{
    int n; vector<Seg> dat;
    //初期化
    SegTree(int _n, vector<int> &a){
        n=1;
        while(n<_n) n*=2;
        dat=vector<Seg>(2*n-1);

        a.resize(n);
        rep(i,n){
            int idx = i+n-1;
            dat[idx] = Seg(i,a[i]);
        }
        for(int i=n-2; i>=0; --i){
            merge(dat[i],dat[2*i+1],dat[2*i+2]);
        }
    }
    //k番目(0-indexed)の値をaに変更
    void update(int k, int a){
        int idx = k;
        k+=n-1;
        dat[k] = Seg(idx,a);

        //更新
        while(k>0){
            k=(k-1)/2;
            merge(dat[k],dat[2*k+1],dat[2*k+2]);
        }
    }
    //内部的に投げられるクエリ
    Seg _query(int a, int b, int k, int l, int r){
        if(r<=a || b<=l) return Seg();

        if(a<=l && r<=b) return dat[k];

        Seg vl=_query(a,b,2*k+1,l,(l+r)/2);
        Seg vr=_query(a,b,2*k+2,(l+r)/2,r);
        Seg ret;
        merge(ret,vl,vr);
        return ret;
    }
    //[a,b)
    ll query(int a, int b){
        return _query(a,b,0,0,n).val;
    }
};

int main(){
    int n,m;
    scanf(" %d %d %d", &n, &m, &x);

    vector<int> a(n);
    rep(i,n) scanf(" %d", &a[i]);

    SegTree st(n,a);
    while(m--){
        int t,p,q;
        scanf(" %d %d %d", &t, &p, &q);
        if(t==1){
            --p;
            st.update(p,q);
        }
        else{
            --p;
            --q;
            printf("%lld\n", st.query(p,q+1));
        }
    }
    return 0;
}

裏紙

ほぼ競プロ、たまに日記

CF 1004 F - Sonya and Bitwise OR

問題

問題概要

アイデア

実装(C++)