信息学奥赛一本通 1539：简单题 | 洛谷 P5057 [CQOI2006] 简单题

【题目链接】

ybt 1539：简单题
洛谷 P5057 [CQOI2006] 简单题

【题目考点】

1. 树状数组

知识点讲解见：洛谷 P3374 【模板】树状数组

【解题思路】

解法1：树状数组

该有01构成数组初值都为0。
某位置的元素被修改奇数次后值为1，被修改偶数次后值为0。
因此只需要求出某位置元素被修改的次数，即可得到该位置的数值。
每次修改是让连续的一段序列翻转，也就是选择数组的一段区间，将该区间中的元素取反（0变为1，1变为0）。
求某元素被修改的次数，就是求有多少个区间覆盖的该元素。
假想存在数组：cL，cR
$c{L}_i$表示区间左端点为i的区间数。
$c{R}_i$表示区间右端点为i的区间数。
$sum{L}_i$：$cL$的前缀和，即左端点L在[1,i]范围内的区间数
$sum{R}_i$：$cR$的前缀和，右端点R在[1,i]范围内的区间数
分别对cL、cR数组建立树状数组treeL与treeR，借助树状数组可以在有单点修改的情况下，以$O(\log n)$时间复杂度求出序列的前缀和。

如果区间[L, R]包含x，则区间左端点L一定小于等于x。
如果区间[L, R]的右端点R小于x，这样的区间的左端点L也一定小于x。
考察左端点$L\le x$的区间，有两类：

• 右端点$R<x$的区间
• 右端点$R\ge x$的区间，即包含x的区间。

左端点$L\le x$的区间数量为$sum{L}_x$。
右端点$R<x$的区间数量为$sum{R}_{x-1}$。
设包含x的区间的数量为$an{s}_x$
有:$sum{L}_x=sum{R}_{x-1}+an{s}_x$
即$an{s}_x=sum{L}_x-sum{R}_{x-1}$

具体做法：

1. 如果需要将区间[l, r]中的元素取反，则存在一个区间$[l,r]$，使$c{L}_l$增加1， $c{R}_r$增加1。树状数组进行相应的单点修改操作。
2. 如果需要查询第x元素的值，则通过$an{s}_x=sum{L}_x-sum{R}_{x-1}$求出x被区间修改的次数$an{s}_x$，如果$an{s}_x$为奇数，第x元素值为1，否则第x元素值为0。

解法2：线段树 维护区间的异或值

考虑对原数字序列进行区间修改、区间查询。
区间修改的操作为对某区间中每个元素都进行01取反，对于由01构成的序列，01取反操作即为xor 1（异或1）操作。
因为$0xor1=1$， $1xor1=0$
区间标记tag设为本段区间中的元素需要被异或的值，即本段区间每个元素实际的值为当前值$xortag$。
注意进行区间修改、单点查询前需要进行标记下传。

【题解代码】

解法1：树状数组

• 写法1：为treeL、treeR设置两套树状数组处理函数

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n, m, treeL[N], treeR[N];//cL[i]：左端点为i的区间数，treeL：cL的树状数组
int lowbit(int x)
{return x & -x;
}
void updateL(int i)//cL[i]++
{for(int x = i; x <= n; x += lowbit(x))treeL[x]++;
}
void updateR(int i)//cR[i]++
{for(int x = i; x <= n; x += lowbit(x))treeR[x]++;
}
int sumL(int i)//cL的前缀和
{int s = 0;for(int x = i; x > 0; x -= lowbit(x))s += treeL[x];return s;
}
int sumR(int i)//cR的前缀和
{int s = 0;for(int x = i; x > 0; x -= lowbit(x))s += treeR[x];return s;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t, l, r, x;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> t;if(t == 1){cin >> l >> r;updateL(l);updateR(r);}else{cin >> x;cout << (sumL(x)-sumR(x-1))%2 << '\n';//初值为0，修改偶数次为0，修改奇数次为1 }}return 0;
}

• 写法2：只设一套树状数组处理函数，传入数组地址

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n, m, treeL[N], treeR[N];//cL[i]：左端点为i的区间数，treeL：cL的树状数组 cR[i]：右端点为i的区间数，treeR：cR的树状数组
int lowbit(int x)
{return x & -x;
}
void update(int i, int *tree)//cL[i]++，或cR[i]++。
{//传入数组名treeL或treeR，可以修改对应传入的tree数组for(int x = i; x <= n; x += lowbit(x))tree[x]++;
}
int sum(int i, int *tree)//求cL或cR的前缀和
{int s = 0;for(int x = i; x > 0; x -= lowbit(x))s += tree[x];return s;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t, l, r, x;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> t;if(t == 1){cin >> l >> r;update(l, treeL);update(r, treeR);}else{cin >> x;//x为题目中的i，求x位置的值 cout << (sum(x, treeL)-sum(x-1, treeR))%2 << '\n';//初值为0，修改偶数次为0，修改奇数次为1 }}return 0;
}

解法2：线段树 维护区间异或值

#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{int val, l, r, tag;
} tree[4*N];
int n, m;
void addTag(int i)
{tree[i].tag ^= 1;tree[i].val ^= 1;
}
void pushDown(int i)
{if(tree[i].tag == 0)return;addTag(2*i);addTag(2*i+1);tree[i].tag = 0;
}
void build(int i, int l, int r)
{tree[i].l = l, tree[i].r = r;if(l == r)//tree[i].val初值都为0 return;int mid = (l+r)/2;build(2*i, l, mid);build(2*i+1, mid+1, r);
}
void update(int i, int l, int r)//a[l]~a[r]取反 
{if(tree[i].r < l || tree[i].l > r)return;if(l <= tree[i].l && tree[i].r <= r)return addTag(i);pushDown(i);update(2*i, l, r);update(2*i+1, l, r);
}
int query(int i, int x)//a[x]
{if(tree[i].l == tree[i].r)return tree[i].val;pushDown(i); if(x <= tree[2*i].r)return query(2*i, x);else//x >= tree[2*i+1].l return query(2*i+1, x);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t, l, r, x;cin >> n >> m;build(1, 1, n);while(m--){cin >> t;if(t == 1){cin >> l >> r;update(1, l, r); }else//t == 2{cin >> x;cout << query(1, x) << '\n';}}return 0;
}