しゃくとり法の条件(ARC098D - Xor Sum 2 )

atcoder.jp

Xor出てきたばっかりだ

いらなかった考察

まず準備としてを求めておく。これによって区間の和が定数時間で求められる。
この前の問題 でも見たように、xorの歩けたが1になる組み合わせはlogNで見つけられるんだよな…でもたし算の組みだけでも網羅できないので〜…
そうだ,a xor bしたものに対してもう一回xor aするとbに戻る、つまりたし算のように区間のxorが定数で求められる。
xor配列を求め、さらに区間の和の配列との差配列を作る。これが同じな二つがあればそこに一区間できる。3つあれば3C2で3区間…iつあればiC2でi(i+2)/2区間生まれる。
と一瞬思ったけど差配列を作るの意味ない。和配列は差で区間出せるだけどxor配列はxorで区間だすので。う〜ん…

いる考察

よく考えたらxorと和でその桁の数が違うの1^1の時だけ。ちゃんと考察すると繰り上がりがある桁がある時その先で整合性を取ることもできず絶対に違う数になる。
これを3つ以上の場合に応用すると、2^kの桁についてその桁が1である数が二個以上あるとsum!=xorとなる。範囲を決めた時その判定は、桁ごとに定数時間で行える。桁も20までなので定数として良い。また「区間の左端を決めた時2^kの桁についてその桁が1である数が1こ以下になる区間の右端」は全てのkについて区間の長さに対して広義単調増加なので、しゃくとり法が使える

区間問題でしゃくとり法使えるかも、みたいな予感がしても最近全然使ってなかったのでどういう時に使えるのかよくわかっていなかったため実際に使うまでに時間かかった。
区間の長さに対して広義単調増加な数を探せばいいのか、なるほど
あとはしゃくとり法は始点の数だけループさせる。なんかどっちも可動にしてたけど意味のないことをしていた。
しゃくとり法のいい復習になった。

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>

 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long

int A[200002];
int A2[21][200002];
int main(void){
    int N;
    
    scanf("%d",&N);
    rep(i,N){
        scanf("%d",&A[i]);
        rep(j,20){
            A2[j][i]= ( A[i]%(int)pow(2,j+1) )/(int)pow(2,j) ;
        }
    }
    rep(i,20){
        rep(j,N){
            if(j>0)A2[i][j]= A2[i][j-1]+A2[i][j];
        }
    }
    ll int ans=0;
    int right=0;
    rep(left,N){
        int num=0;
        while(num<2){
            rep(i,20){
                left==0? num=A2[i][right] : num=A2[i][right]-A2[i][left-1];
                if(num>=2){
                    ans+=right-left;right--;
                    break;
                }
            }
            if(num<=1){
                if(right==N-1){
                    ans+=N-left;num=2;
                }else{
                    right++;
                }
            }
        }
    }
    printf("%lld\n",ans);
}