CFR Educational 12 E. Beautiful Subarrays ( Trie XOR )

Problem - E - Codeforces
pekempeyさんの記事が参考になりました。ありがとうございます。
pekempey.hatenablog.com
Trie はあまり慣れなかったのでいい練習になった。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 6;
const int MAXK = 1e9 + 9;
const int MAXA = 1e9 + 9;
const int LOGA = 30 + 1;
typedef long long ll;

int N, K;
int A[ MAXN ];

struct Trie{
    int occ;
    Trie *ch[ 2 ];
    Trie(){
        occ = 0;
        for( int i = 0; i < 2; ++i )
            ch[ i ] = NULL;
    }
    void add( int v, int h ){
        ++occ;
        if( h == 0 ) return;
        int f = v >> h - 1 & 1;
        if( !ch[ f ] ) ch[ f ] = new Trie();
        ch[ f ]->add( v, h - 1 );
    }
    int query( int v, int x, int h ){ // matching with, current value for trie, confirmed digit
        int res = 0;
        int t = v ^ x;
        int mask = ( 1 << h ) - 1; // 1s for not sure part
        int maxv = t | mask;
        int minv = t & ~mask;
        if( maxv < K ) return 0;
        if( minv >= K ) return occ;
        if( ch[ 0 ] ) res += ch[ 0 ]->query( v, x, h - 1 );
        if( ch[ 1 ] ) res += ch[ 1 ]->query( v, x | 1 << h - 1, h - 1 );
        return res;
    }
};

void solve(){
    Trie *trie = new Trie();
    ll ans = 0;
    int p = 0;
    for( int i = 0; i < N; ++i ){
        trie->add( p, LOGA - 1 );
        p ^= A[ i ];
        ans += trie->query( p, 0, LOGA - 1 );
    }
    cout << ans << "\n";
}

int main(){
    scanf( "%d%d", &N, &K );
    for( int i = 0; i < N; ++i )
        scanf( "%d", A + i );
    solve();
    return 0;
}