#1177830 (C++23(gcc16)) No.3569 Xor to Zero

• 問題: No.3569 Xor to Zero
• ユーザー: Aob-11
• 提出日時: 2026-08-21 12:10:10
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 217 ms / 2,000 ms
• コード長: 6,007 bytes
• コンパイル時間: 2,527 ms
• コンパイル使用メモリ: 355,548 KB
• 実行使用メモリ: 18,560 KB
• 最終ジャッジ日時: 2026-08-21 12:10:21
• 合計ジャッジ時間: 8,300 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 25

ソースコード

#include <bits/stdc++.h>



using namespace std;

#define DB double
#define LL long long
#define ULL unsigned long long
#define uint unsigned int
#define in128 int128
#define cint const int
#define cLL const LL
#define For(z,e1,e2) for(int z=(e1);z<=(e2);z++)
#define Rof(z,e1,e2) for(int z=(e2);z>=(e1);z--)

#define inint(e) scanf("%d",&e)
#define inll(e) scanf("%lld",&e)
#define inpr(e1,e2) scanf("%d%d",&e1,&e2)
#define in3(e1,e2,e3) scanf("%d%d%d",&e1,&e2,&e3)
#define outint(e) printf("%d\n",e)
#define outll(e) printf("%lld\n",e)
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return
#define pb push_back
#define ft first
#define sc second
#define pii pair<int,int>
#define pli pair<long long,int>
#define pil pair<int,long long>
#define vct vector
#define clean(e) while(!e.empty()) e.pop()
#define all(ev) ev.begin(),ev.end()
#define sz(ev) ((int)ev.size())

cLL mod=998244353ll,G=404ll;
template <typename Type> void get_min(Type &w1,const Type w2) { if(w2<w1) w1=w2; } 
template <typename Type> void get_max(Type &w1,const Type w2) { if(w2>w1) w1=w2; }
template <typename Type> Type md(Type w1,const Type w2=mod) { w1%=w2; if(w1<(Type)0) w1+=w2; return w1; } 
void Add(LL &X_,cLL Y_,cLL M_=mod) { if((X_+=Y_)>=M_) X_-=M_; }

mt19937 gen(time(NULL));
int rnd(int l,int r) { return (int)(gen()%(r-l+1)+l); }
mt19937_64 genll(time(NULL));
LL rndll(LL l,LL r) { return (LL)(genll()%(r-l+1ll)+l); }

void main_init()
{

}

cint MAX_NODES = 4000005; 
cint MAX_BIT = 30;

struct Node {
    int ch[2];
    int sz;
    int add_x;
    int set_x;
    LL sum_x;
} tr[MAX_NODES];

int bin[MAX_NODES], bin_top;
int tot;

int new_node() {
    int u = bin_top ? bin[bin_top--] : ++tot;
    tr[u].ch[0] = tr[u].ch[1] = 0;
    tr[u].sz = 0;
    tr[u].sum_x = 0;
    tr[u].add_x = 0;
    tr[u].set_x = -1;
    return u;
}

void recycle(int u) {
    if (u) bin[++bin_top] = u;
}

void apply_set(int u, int val) {
    if (!u) return;
    tr[u].set_x = val;
    tr[u].add_x = 0;
    tr[u].sum_x = (LL)tr[u].sz * val;
}

void apply_add(int u, int val) {
    if (!u) return;
    if (tr[u].set_x != -1) {
        tr[u].set_x += val;
    } else {
        tr[u].add_x += val;
    }
    tr[u].sum_x += (LL)tr[u].sz * val;
}

void pushdown(int u) {
    if (tr[u].set_x != -1) {
        apply_set(tr[u].ch[0], tr[u].set_x);
        apply_set(tr[u].ch[1], tr[u].set_x);
        tr[u].set_x = -1;
    }
    if (tr[u].add_x != 0) {
        apply_add(tr[u].ch[0], tr[u].add_x);
        apply_add(tr[u].ch[1], tr[u].add_x);
        tr[u].add_x = 0;
    }
}

void pushup(int u) {
    tr[u].sz = 0;
    tr[u].sum_x = 0;
    if (tr[u].ch[0]) {
        tr[u].sz += tr[tr[u].ch[0]].sz;
        tr[u].sum_x += tr[tr[u].ch[0]].sum_x;
    }
    if (tr[u].ch[1]) {
        tr[u].sz += tr[tr[u].ch[1]].sz;
        tr[u].sum_x += tr[tr[u].ch[1]].sum_x;
    }
}

void insert(int &u, int val, int bit, int x_val) {
    if (!u) u = new_node();
    if (bit < 0) {
        tr[u].sz++;
        tr[u].sum_x += x_val;
        return;
    }
    pushdown(u);
    int b = (val >> bit) & 1;
    insert(tr[u].ch[b], val, bit - 1, x_val);
    pushup(u);
}


void split(int u, int &u_lt, int &u_ge, int v, int tag, int bit) {
    if (!u) { u_lt = u_ge = 0; return; }
    if (bit < 0) { u_lt = 0; u_ge = u; return; }
    pushdown(u);
    int b_v = (v >> bit) & 1;
    int b_tag = (tag >> bit) & 1;
    int act0 = b_tag;
    if (b_v == 1) {
        u_lt = u;
        u_ge = new_node();
        int dir_0 = (act0 == 0) ? 0 : 1;
        int dir_1 = 1 ^ dir_0;
        int ch_lt = 0, ch_ge = 0;
        split(tr[u].ch[dir_1], ch_lt, ch_ge, v, tag, bit - 1);
        tr[u_lt].ch[dir_1] = ch_lt;
        tr[u_ge].ch[dir_1] = ch_ge;
        tr[u_ge].ch[dir_0] = 0; 
        pushup(u_lt);
        pushup(u_ge);
        if (tr[u_lt].sz == 0) { recycle(u_lt); u_lt = 0; }
        if (tr[u_ge].sz == 0) { recycle(u_ge); u_ge = 0; }
    } else {
        u_lt = new_node();
        u_ge = u;
        int dir_0 = (act0 == 0) ? 0 : 1;
        int dir_1 = 1 ^ dir_0;
        int ch_lt = 0, ch_ge = 0;
        split(tr[u].ch[dir_0], ch_lt, ch_ge, v, tag, bit - 1);
        tr[u_ge].ch[dir_0] = ch_ge;
        tr[u_lt].ch[dir_0] = ch_lt;
        tr[u_lt].ch[dir_1] = 0;
        pushup(u_lt);
        pushup(u_ge);
        if (tr[u_lt].sz == 0) { recycle(u_lt); u_lt = 0; }
        if (tr[u_ge].sz == 0) { recycle(u_ge); u_ge = 0; }
    }
}

int merge(int u, int v, int bit) {
    if (!u || !v) return u | v;
    if (bit < 0) {
        tr[u].sz += tr[v].sz;
        tr[u].sum_x += tr[v].sum_x;
        recycle(v);
        return u;
    }
    pushdown(u); pushdown(v);
    tr[u].ch[0] = merge(tr[u].ch[0], tr[v].ch[0], bit - 1);
    tr[u].ch[1] = merge(tr[u].ch[1], tr[v].ch[1], bit - 1);
    pushup(u);
    recycle(v); 
    if (tr[u].sz == 0) { recycle(u); return 0; }
    return u;
}

cint N=1.02e5;
int n;
int a[N];

void main_solve()
{
    inint(n);
    for(int i = 1; i <= n; i++) inint(a[i]);
    tot = 0;
    bin_top = 0;
    int Trie[2] = {0, 0};
    int TAG = 0;
    LL ans = 0ll;
    for(int i = n; i >= 1; i--) {
        insert(Trie[1], TAG, MAX_BIT, 0);
        int T0_lt = 0, T0_ge = 0;
        split(Trie[0], T0_lt, T0_ge, a[i], TAG, MAX_BIT);
        int T1_lt = 0, T1_ge = 0;
        split(Trie[1], T1_lt, T1_ge, a[i], TAG, MAX_BIT);
        apply_set(T0_lt, 1);
        apply_set(T1_lt, 1);
        apply_add(T0_ge, 1);
        if (a[i] == 1) apply_add(T1_ge, 1);
        else apply_add(T1_ge, 2);
        int new_T0 = 0, new_T1 = 0;
        if (a[i] == 1) new_T0 = T1_ge;
        else new_T0 = 0;
        new_T1 = T0_lt;
        new_T1 = merge(new_T1, T1_lt, MAX_BIT);
        new_T1 = merge(new_T1, T0_ge, MAX_BIT);
        if (a[i] != 1) new_T1 = merge(new_T1, T1_ge, MAX_BIT);
        Trie[0] = new_T0;
        Trie[1] = new_T1;
        ans += (Trie[0] ? tr[Trie[0]].sum_x : 0) + (Trie[1] ? tr[Trie[1]].sum_x : 0);
        TAG ^= a[i];
    }
    outll(ans);
}

int main()
{
    main_init();
    main_solve();
    return 0;
}