题解 | 单点修改与区间非平凡异或和 #

$[线段树+思维]$

给定长度为 $n$ 的 $a$ 数组，执行两种操作：

单点修改：将 $i$ 这个位置上的元素修改为 $x$ ，即 $a_{i}\rightarrow x$
区间非平凡异或和查询：输出下标在 $[l,r]$ 这个区间的所有连续子数列的异或和的异或和，即 $\oplus_{i=l}^{r} \oplus_{j=i}^{r}(\oplus_{k=i}^{j}a_{k})$

容易发现的规律：例如 $a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}$ :
$a_{i}$ 在连续子序列中出现的次数一共为 (左边数字的个数 + 1) $\times$ (右边数字的个数 + 1)

如果区间 $[l,r]$ 的长度为偶数，那么以 $a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}$ 为例子，那么 $a_{1}$ 出现的次数为 $(0 +1)\times (5+1)$ ，那么 $a_{2}$ 出现的次数为 $(1 +1)\times (4+1)$ .....

那么出现的次数是 $奇数\times 偶数$ ， $偶数\times 奇数$ ， $奇数\times 偶数$ .....，因为偶数个相同的数字异或结果为0，那么所以 $[l,r]$ 的长度为偶数时，结果直接等于0

如果区间 $[l,r]$ 的长度为奇数，那么就是 $偶数\times 偶数$ ， $奇数\times 奇数$ ， $偶数\times 偶数$ ， $奇数\times 奇数$ .....交替，即要么是区间 $[l,r]$ 所有下标为偶数的值异或，要么是所有下标为奇数的值异或

所以线段树需要维护区间的奇数异或值以及偶数异或值

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 2e5 + 10;

struct Node{
    int l, r;
    int x, sum_ji, sum_ou;
}tr[4 * N];

int n, q, a[N];

void push_up(int u){
    tr[u].sum_ji = tr[u << 1].sum_ji ^ tr[u << 1 | 1].sum_ji;
    tr[u].sum_ou = tr[u << 1].sum_ou ^ tr[u << 1 | 1].sum_ou;
}

void build(int u, int l, int r){
    if(l == r){
        if(l & 1) tr[u] = {l, r, a[l], a[l], 0};
        else tr[u] = {l, r, a[l], 0, a[l]};
        return ;
    }
    else{
        tr[u] = {l, r, 0, 0, 0};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
}

void modify(int u, int pos, int v){
    if(tr[u].l == pos && pos == tr[u].r){
        tr[u].x = v;
        if(pos & 1) tr[u].sum_ji = v;
        else tr[u].sum_ou = v;
    }
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(pos <= mid) modify(u << 1, pos, v);
        else modify(u << 1 | 1, pos, v);
        push_up(u);
    }
}

int query(int u, int l, int r, int type){
    if(l <= tr[u].l && tr[u].r <= r){
        if(type == 0) return tr[u].sum_ou;
        else return tr[u].sum_ji;
    }
    else{
        int res = 0;
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) res = res ^ query(u << 1, l, r, type);
        if(r > mid) res = res ^ query(u << 1 | 1, l, r, type);
        return res;
    }
}

signed main(){
    HelloWorld;
    
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    build(1, 1, n);

    while(q --){
        int op; cin >> op;
        if(op == 1){
            int pos, x; cin >> pos >> x;
            modify(1, pos, x);
        }
        else{
            int l, r; cin >> l >> r;
            int len = r - l + 1;
            if(!(len & 1)) cout << "0" << endl;
            else{
                if(l & 1) cout << query(1, l, r, 1) << endl;
                else cout << query(1, l, r, 0) << endl;
            }
        }
    }
    return 0;
}