题解 P6225 【[eJOI2019]异或橙子】
囧仙
2020-08-06 21:29:04
发现本题目前所有题解都是 树状数组 + 分奇偶分别维护，就我傻乎乎地直接用一颗线段树维护，深感奇妙，于是来写一下线段树的做法
- 分析询问
首先，可以发现下标 $i$ 的数会被 $(i - l + 1) \times (r - i + 1)$ 个区间包含
因为对答案异或偶数次一个数不会产生影响，对答案异或奇数次一个数等同于对答案异或一次这个数，所以也就是查询所有 $(i - l + 1) \times (r - i + 1)$ 为奇数的数的异或和
因为 奇数 $\times$ 奇数 $=$ 奇数，偶数 $\times$ 奇数 $=$ 偶数，偶数 $\times$ 偶数 $=$ 偶数，所以 $(i - l + 1) \times (r - i + 1)$ 为奇数 的条件是 $i - l + 1,r - i + 1$ 都为奇数
所以 $i - l,r - i$ 都为偶数
所有满足 $i - l$ 为偶数的下标可以表示为 $l + 2k$，所以满足 $r - i$ 为偶数的下标可以表示为 $r - 2k$
不难发现，若 $2 \nmid r- l$，那么不存在同时满足这两个条件的下标
若 $2 \nmid r - l$，那么满足这两个条件的下标实际上就是 $l + 2k$
- 如何用一颗线段树如何维护这个操作
现在要干这两件事：
- 单点修改
- 查询 $[l,r]$ 中所有奇偶性与 $l$ 相同的数的 $\operatorname{xor}$ 和
那么显然要对线段树上的每个节点维护，与其左端点奇偶性相同的数的 $\operatorname{xor}$ 和 $val_0$ ，以及与其左端点奇偶性不同的数的 $\operatorname{xor}$ 和 $val_1$
考虑如何 $pushup$：
- 如果左子区间的长度是 $2$ 的倍数
那么实际上 $val_{fa,0} = val_{ls,0} \operatorname{xor} val_{rs,0}$
$val_{fa,1} = val_{ls,1} \operatorname{xor} val_{rs,1}$
- 如果左子区间得长度不是 $2$ 的倍数
$val_{fa,0} = val_{ls,0} \operatorname{xor} val_{rs,1}$
$val_{fa,1} = val_{ls,1} \operatorname{xor} val_{rs,0}$
同理，在进行查询的时候，可能你查询的区间是与当前节点左段点奇偶性相同的，也可能不是，要进行分类讨论
在将一个查询分解到对于左右儿子的查询时，也要进行分类讨论，具体看代码：
```cpp
#include <cstdio>
int n,q;
struct node{
int len,val[2];//val[0] 含区间左端点,val[1] 不含区间左端点
}tree[800005];
#define ls (rt * 2)
#define rs (rt * 2 + 1)
void pushup(int rt){
if(tree[ls].len % 2 == 0){
tree[rt].val[0] = tree[ls].val[0] ^ tree[rs].val[0];
tree[rt].val[1] = tree[ls].val[1] ^ tree[rs].val[1];
}else{
tree[rt].val[0] = tree[ls].val[0] ^ tree[rs].val[1];
tree[rt].val[1] = tree[ls].val[1] ^ tree[rs].val[0];
}
}
void build(int rt,int l,int r){
tree[rt].len = r - l + 1;
if(l == r){
scanf("%d",&tree[rt].val[0]);
return;
}
int mid = l + r >> 1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
void modify(int rt,int l,int r,int id,int C){
if(l == r){
tree[rt].val[0] = C;
return;
}
int mid = l + r >> 1;
if(id <= mid){
modify(ls,l,mid,id,C);
}else{
modify(rs,mid+1,r,id,C);
}
pushup(rt);
}
int query(int rt,int l,int r,int L,int R,int op){//op = 0 含左端点,op = 1 不含左端点
if(l == L && r == R) return tree[rt].val[op];
int mid = l + r >> 1;
if(R <= mid){
return query(ls,l,mid,L,R,op);
}else if(L > mid){
return query(rs,mid+1,r,L,R,op);
}else{
if((mid - L + 1) % 2 == 0){
return query(ls,l,mid,L,mid,op) ^ query(rs,mid+1,r,mid+1,R,op);
}else{
return query(ls,l,mid,L,mid,op) ^ query(rs,mid+1,r,mid+1,R,!op);
}
}
}
int main(){
scanf("%d%d",&n,&q);
build(1,1,n);
int op,l,r,x,y;
for(int i = 1;i <= q;i++){
scanf("%d",&op);
if(op == 1){
scanf("%d%d",&x,&y);
modify(1,1,n,x,y);
}else{
scanf("%d%d",&l,&r);
if((r - l) % 2){
printf("0\n");
}else{
printf("%d\n",query(1,1,n,l,r,0));
}
}
}
return 0;
}
```
- 这个做法有什么用
实际上在本题中，它是完全劣于那个树状数组分奇偶性分别维护的做法的
但是在一些题目中，就会只能用这个做法，比如我曾经做过一道题，题目大意是：
给你一个序列，初始所有点的值都为 $0$，动态修改点权，保证左边的点的权值大于等于右边的权值，多次查询 $[1,x]$ 前缀内最多选 $k$ 个点，且没有两个点相邻的最大点权和
这个时候就只能对于线段树上每个节点分类讨论，记录是否能选最左边的点，是否能选最右边的点的最大独立点权和，然后每次查询在线段树上二分了
所以这个做法是更具拓展性的