P6225 异或橙子

问题

P6225 异或橙子
给定一个序列，有两种操作，一种是修改 $a[x]$ 为 $y$，一种是询问 $[l, r]$ 的所有子区间异或值的异或和。

数据规模：$n, q \le 2e5$。

首先发现这是一个区间的异或和问题，而异或与加法的性质类似，均符合前缀和条件。而这又是一个动态修改，动态查询的问题，所以我们考虑树状数组来维护。

由于比较麻烦的一点是要求区间内所有子区间的异或值的异或和，所以我们可以统计每个点 $a_{i}$ 对答案的贡献。

对于 $l \le i \le r$ 来说，包含 $a_{i}$ 的子区间数量为：$(i-l+1) \cdot (r-i+1)$；由于异或的特性，出现偶数次的元素会相互抵消，所以只有奇数的情况会被保留，而奇数 = 奇数 $\times$ 奇数，也就是说 $l$ 和 $r$ 的奇偶性要相同。

于是我们分别维护奇数下标和偶数下标的异或和就行了。

▶

P6225

struct BIT {
/* ======================================== */
ll tr[maxn];
int sz;
void init( int N ) { sz = N;
    fill( tr, tr + sz + 2, 0 );
}
void add( int idx, ll val ) {
    for( int i = idx; i <= sz; i += i & -i ) tr[i] ^= val;
}
ll ask( int idx ) {
    ll res = 0;
    for( int i = idx; i; i -= i & -i ) res ^= tr[i];
    return res;
}
ll query( int l, int r ) { return ask( r ) ^ ask( l - 1 ); }
/* ======================================== */
} bit[2];

int a[maxn];

void solve( ) {
    int n = read( ), q = read( );
    bit[0].init( n );
    bit[1].init( n );

    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        bit[i & 1].add( i, a[i] );
    }

    while( q -- ) {
        int opt = read( );

        if( opt == 1 ) {
            int x = read( ), y = read( );
            bit[x & 1].add( x, a[x] );
            bit[x & 1].add( x, y );
            a[x] = y;
        }
        else {
            int l = read( ), r = read( );
            int len = r - l + 1;
            if( len % 2 == 0 ) {
                cout << 0 << '\n';
            } else {
                cout << bit[l & 1].query( l, r ) << '\n';
            }
        }
    }
}