#1168430 (C++14) No.3569 Xor to Zero

• 問題: No.3569 Xor to Zero
• ユーザー: hos.lyric
• 提出日時: 2026-06-06 01:37:39
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,627 ms / 2,000 ms
• コード長: 4,785 bytes
• コンパイル時間: 2,016 ms
• コンパイル使用メモリ: 144,500 KB
• 実行使用メモリ: 332,032 KB
• 最終ジャッジ日時: 2026-06-06 01:37:59
• 合計ジャッジ時間: 20,439 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

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

ソースコード

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T> ostream &operator<<(ostream &os, const vector<T> &as);
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


int N;
vector<int> A;

Int brute() {
  Int ans = 0;
  for (int r = N; r > 0; --r) {
    Int f = 0;
    Int xum = 0;
    for (int l = r; --l >= 0; ) {
      const int a = A[l];
      if (xum < a) {
        f = 1;
      } else {
        if (f & 1) {
          if (a == 1) {
            f += 1;
          } else {
            f += 2;
          }
        } else {
          f += 1;
        }
      }
      xum ^= a;
// cerr<<"["<<l<<", "<<r<<"): "<<f<<" "<<xum<<endl;
      ans += f;
    }
  }
  return ans;
}

#define rep(x) for (int x = 0; x < 4; ++x)

// (even, odd), (sum *^0, sum *^1)
struct Node {
  // even sum0, even sum1, odd sum0, odd sum1
  Int a[4];
  Int lz[4][4];
  Node() : a{}, lz{} {
    rep(x) lz[x][x] = 1;
  }
  void push(Node &l, Node &r) {
    l.mul(lz);
    r.mul(lz);
    rep(x) rep(y) lz[x][y] = (x == y) ? 1 : 0;
  }
  void pull(const Node &l, const Node &r) {
    rep(x) a[x] = l.a[x] + r.a[x];
  }
  void mul(const Int f[4][4]) {
    Int b[4] = {};
    rep(x) rep(y) b[x] += f[x][y] * a[y];
    rep(x) a[x] = b[x];
    Int g[4][4] = {};
    rep(x) rep(z) if (f[x][z]) rep(y) g[x][y] += f[x][z] * lz[z][y];
    rep(x) rep(y) lz[x][y] = g[x][y];
  }
  // leaf
  void add0() {
    a[0] += 1;
  }
};

int E;
Node seg[1 << 21];

void push(int u) {
  assert(u < 1 << E);
  seg[u].push(seg[u << 1], seg[u << 1 | 1]);
}
void pull(int u) {
  assert(u < 1 << E);
  seg[u].pull(seg[u << 1], seg[u << 1 | 1]);
}

// f <- 1  for  (x XOR b) < a
void ch0(int e, int u, int a, int b, const Int f[4][4]) {
  if (!e) {
    return;
  }
  --e;
  push(u);
  const int v0 = u << 1 | (b >> e & 1);
  const int v1 = v0 ^ 1;
  if (!(a >> e & 1)) {
    ch0(e, v0, a, b, f);
  } else {
    seg[v0].mul(f);
    ch0(e, v1, a, b, f);
  }
  pull(u);
}
// f <- f + (1 or 2)  for  (x XOR b) >= a
void ch1(int e, int u, int a, int b, const Int f[4][4]) {
  if (!e) {
    seg[u].mul(f);
    return;
  }
  --e;
  push(u);
  const int v0 = u << 1 | (b >> e & 1);
  const int v1 = v0 ^ 1;
  if (!(a >> e & 1)) {
    ch1(e, v0, a, b, f);
    seg[v1].mul(f);
  } else {
    ch1(e, v1, a, b, f);
  }
  pull(u);
}

void chLeaf(int e, int u, int b) {
  if (!e) {
    seg[u].add0();
    return;
  }
  --e;
  push(u);
  chLeaf(e, u << 1 | (b >> e & 1), b);
  pull(u);
}

int main() {
  for (; ~scanf("%d", &N); ) {
    A.resize(N);
    for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
    
    const int maxA = *max_element(A.begin(), A.end());
    for (E = 1; !(maxA < 1 << E); ++E) {}
    
    vector<int> AXum(N + 1, 0);
    for (int i = 0; i < N; ++i) AXum[i + 1] = AXum[i] ^ A[i];
    
    for (int u = 1; u < 1 << (E+1); ++u) seg[u] = Node();
    
    Int ans = 0;
    for (int i = N; --i >= 0; ) {
      chLeaf(E, 1, AXum[i + 1]);
      Int f[4][4] = {}, g[4][4] = {};
      // =1
      f[2][0] = f[2][2] = f[3][0] = f[3][2] = 1;
      if (A[i] == 1) {
        // +1
        g[0][2] = g[1][2] = g[1][3] = 1;
        g[2][0] = g[3][0] = g[3][1] = 1;
      } else {
        // +1 if even, +2 if odd
        g[2][0] = g[2][2] = g[3][1] = g[3][3] = 1;
        g[3][0] = 1;
        g[3][2] = 2;
      }
      ch0(E, 1, A[i], AXum[i + 1], f);
      ch1(E, 1, A[i], AXum[i + 1], g);
// cerr<<"i = "<<i<<": ";pv(seg[1].a,seg[1].a+4);
      ans += seg[1].a[1] + seg[1].a[3];
    }
    printf("%lld\n", ans);
#ifdef LOCAL
const Int brt=brute();
if(brt!=ans){
 cerr<<"FAIL A = "<<A<<endl;
 cerr<<"brt = "<<brt<<endl;
 cerr<<"ans = "<<ans<<endl;
 assert(false);
}
#endif
  }
  return 0;
}