#1176335 (C++23(gcc16)) No.3205 Range Pairwise Xor Query

• 問題: No.3205 Range Pairwise Xor Query
• ユーザー: Dương Nguyễn
• 提出日時: 2026-08-12 12:39:39
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 3,995 bytes
• コンパイル時間: 5,564 ms
• コンパイル使用メモリ: 363,512 KB
• 実行使用メモリ: 23,680 KB
• 最終ジャッジ日時: 2026-08-12 12:40:03
• 合計ジャッジ時間: 13,743 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	WA * 1
other	RE * 20

ソースコード

#include<bits/stdc++.h>

#define TASK "text"
#define all(x) x.begin(), x.end()
#define compact(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define fi first
#define se second
#define ___Speacial_ signed main()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int N = 1e6 + 7;

int a[N];
int freq[2 * N], pos[2 * N], elms[2 * N];
int n, q, block, base, Sz; 

struct Fenwick {
    using _data = int;
    vector<_data> bit;
    int n;

    Fenwick() {}
    Fenwick(int _n) {
        n = _n;
        bit.assign(n + 1, 0);
    }

    void update(int i, _data delta) {
        if (i <= 0 || i > n) return;
        for (; i <= n; i += i & -i) { bit[i] += delta; }
    }

    _data get(int i) {
        if (i > n) i = n;
        if (i <= 0) return 0;
        _data res = 0;
        for (; i > 0; i &= i - 1) { res += bit[i]; }
        return res;
    }

    _data query(int l, int r) {
        if (r < 0) return 0;
        if (l <= 0) return get(r);
        return get(r) - get(l - 1);
    }
} fw(1 << 22);

struct Query {
    int l, r, id;

    bool operator < (const Query& other) const {
        if (l / block != other.l / block)
            return l / block < other.l / block;
        return ((l / block) & 1) ? (r < other.r) : (r > other.r);
    }
};

inline void add_odd(int x) {
    elms[Sz] = x;pos[x] = Sz++;
}

inline void sub_odd(int x) {
    int p = pos[x];
    int last_elm = elms[Sz - 1];
    elms[p] = last_elm;
    pos[last_elm] = p;
    Sz--;
}

inline void add(int idx) {
    int x = a[idx];
    ll self = 1ll * freq[x] * (freq[x] - 1) / 2;
    if (self & 1) base ^= (x * 2);
    if (freq[x] & 1) sub_odd(x);
    
    freq[x]++;
    
    self = 1ll * freq[x] * (freq[x] - 1) / 2;
    if (self & 1) base ^= (x * 2);
    if (freq[x] & 1) add_odd(x);
}

inline void sub(int idx) {
    int x = a[idx];
    ll self = 1ll * freq[x] * (freq[x] - 1) / 2;
    if (self & 1) base ^= (x * 2);
    if (freq[x] & 1) sub_odd(x);
    
    freq[x]--;
    
    self = 1ll * freq[x] * (freq[x] - 1) / 2;
    if (self & 1) base ^= (x * 2);
    if (freq[x] & 1) add_odd(x);
}

___Speacial_ {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(TASK".inp","r")){
        freopen(TASK".inp","r",stdin);
        freopen(TASK".out","w",stdout);
    }
    
    cin >> n;
    int testcases = 1;   
    cin >> testcases;
    
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    block = max(1, (int)(n / sqrt(testcases)));
    vector<Query> queries(testcases);
    for (int i = 0; i < testcases; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }

    sort(all(queries));
    vector<int> res(testcases);
    int currentL = 1, currentR = 0;

    for (int i = 0; i < testcases; ++i) {
        int L = queries[i].l, R = queries[i].r;

        while (currentL > L) { currentL--; add(currentL); }
        while (currentR < R) { currentR++; add(currentR); }
        while (currentL < L) { sub(currentL); currentL++; }
        while (currentR > R) { sub(currentR); currentR--; }

        int ans = base;
        
        for (int k = 20; k >= 0; --k) { 
            int full = (1 << (k + 1)) - 1;
            int pL = (1 << k), pR = full;
            ll cnt = 0;
            
            for (int j = 0; j < Sz; ++j) {
                int x = elms[j];
                int v = x & full;
                cnt += fw.query(pL - v + 1, pR - v + 1);
                cnt += fw.query(pL + full + 1 - v + 1, pR + full + 1 - v + 1);
                fw.update(v + 1, 1);
            }

            if (cnt & 1) ans ^= (1 << k); 
            
            for (int j = 0; j < Sz; ++j) {
                int x = elms[j];
                fw.update((x & full) + 1, -1);
            }
        }   
        res[queries[i].id] = ans;
    }

    for (int i = 0; i < testcases; ++i) {
        cout << res[i] << '\n';
    }

    cerr << "[Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " ms.]\n";
    return 0;
}