信息学奥赛一本通 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;
}