title

LOJ 3195

analysis

首先明确一个东西， 一个数如果被异或奇数次，才会对结果做出贡献。

所以对于查询操作，手玩发现：

1. 对于不同奇偶性 \(l,r\) ，这段区间中的每个数在答案里都出现了偶数次，也就是被异或了偶数次，那么最大后答案便为 \(0\) ；
2. 对于同奇偶性 \(l,r\) ， 与区间端点奇偶性相同的位置上的数会被异或奇数次，从而对答案产生贡献，而其余位置则会被异或偶数次，不会对答案产生贡献 。

所以加上之前的单点修改，和这个区间异或和，可以使用 \(BIT\) 快速单点修改，查询来解决。

（另外，对于压行使用三目运算符的同学，多加小括号，可以避免很多意外。）

code

#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

#define DeBug(x) std::cout << #x << " = " << x << std::endl

const int MaxN = 2e5 + 10;

namespace IO
{
    #define G ch = getchar()
    char buf[1<<15], *fs, *ft;
    inline char getc() { return ft == fs && (ft = (fs = buf) + fread(buf, 1, 1 << 15, stdin), ft == fs) ? 0 : *fs ++; }
    template <typename T> inline void read(T &x)
    {
        x = 0;
        T f = 1, G;
        while (!isdigit(ch) && ch ^ '-') G;
        if (ch == '-') f = -1, G;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), G;
        x *= f;
    }

    template <typename T, typename... Args>
    inline void read(T &x, Args &...args) { read(x); read(args...); }

    char Out[1<<24], *fe = Out;
    inline void flush() { fwrite(Out, 1, fe - Out, stdout); fe = Out; }
    template <typename T> inline void write(T x, char str)
    {
        if (!x) *fe++ = 48;
        if (x < 0) *fe++ = '-', x = -x;
        T num = 0, ch[20];
        while (x) ch[++ num] = x % 10 + 48, x /= 10;
        while (num) *fe++ = ch[num --];
        *fe++ = str;
    }
}

using IO::read;
using IO::write;

template <typename T> inline bool chkMin(T &a, const T &b) { return a > b ? (a = b, true) : false; }
template <typename T> inline bool chkMax(T &a, const T &b) { return a < b ? (a = b, true) : false; }
template <typename T> inline T min(T a, T b) { return a < b ? a : b; }
template <typename T> inline T max(T a, T b) { return a > b ? a : b; }

int n, q;
struct BIT
{
    int c[MaxN];
    inline int lowbit(int x) { return x & -x; }
    inline void add(int x, int k) { while (x <= n) c[x] ^= k, x += lowbit(x); }
    inline int ask(int x) { int ans = 0; while (x) ans ^= c[x], x -= lowbit(x); return ans; }
} O, E;//奇偶

int a[MaxN];
int main()
{
    read(n, q);
    for (int i = 1; i <= n; ++ i) read(a[i]), i & 1 ? O.add(i, a[i]) : E.add(i, a[i]);
    for (int i = 1, opt, x, y; i <= q; ++ i)
    {
        read(opt, x, y);
        if (opt == 1) x & 1 ? (O.add(x, a[x]), O.add(x, a[x] = y)) : (E.add(x, a[x]), E.add(x, a[x] = y));
        else write( ((x + y) & 1) ? 0 : (x & 1 ? (O.ask(y) ^ O.ask(x - 1)) : (E.ask(y) ^ E.ask(x - 1))), '\n');
    }
    IO::flush();
    return 0;
}

LOJ #3195. 「eJOI2019」异或橙子 BIT

原文：https://www.cnblogs.com/G-hsm/p/LOJ3195.html