ARC098 D - Xor Sum2

問題概要

長さNの整数列Aがある.
二点l, r ( l < r )を決めて, ~ を全て足した値と全て xor した値が等しい l と r の組みの個数を求めろ.

解法

制約が2*10⁵なので0(n²)解は無理っぽそうなので,O(n)かO(nlog(n))ぐらいかなぁって気持ちになれるけど,コンテスト中は解法は降ってこなかった. 結論を言うと ~ の整数のうち, 各bitの立っている整数の個数が1個以下だと 和 と xor が等しくなる. と言うこと.

例えば, 2 と 10 だと, 2進数にすると 0010 と 1010 となる. これの和は 1100 , xor は1000になる. ここで等しくならない原因は,同じ場所のbitが2つ以上立っていると, 和では繰り上がらなければいけないところが xor では繰り上がらず0になってしまうので和と xor は等しくならなくなってしまうことだ.

これをどうやって数えるかと言うとしゃくとり法を使えばいいみたい . しゃくとり法は0(n)なのでACできる.

ソースコード

int main(){
    long long n,ans=0;
    int a[2000005];

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    long long xsum=0,sum=0;

    int r=0;
    for(int l=0;l<n;l++){
        while(r<n){
            if((xsum ^ a[r])!=(sum + a[r]))break;
            xsum=(a[r] ^ xsum);
            sum+=a[r];
            r++;
        }
        ans+=(r-l);
        xsum^=a[l];
        sum-=a[l];
    }
    cout<<ans<<endl;
    return 0;
}

tourist解

これは解説のO(n)解なのかな？

各bitが最後に立っていたのはいつかを記録する配列を用意しておき,更新するタイミングでその時間のmaxをとってあげればi-max+1でiまでの題意をみたす個数がもとまる.

正直これ書いてて自分で何言ってるのかわからなくなったので,ソースコードを見れば一瞬でわかると思います.感動しました.

一言

解説ブログを書きまくって解説するのうまくなってやるぞい！！