当前位置：首页 > news >正文

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

news 来源：原创 2025/7/20 11:40:59

【题目链接】

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

【题目考点】

1. 树状数组

模板题及讲解：洛谷 P3374 【模板】树状数组

【解题思路】

解法1：树状数组

该有01构成数组初值都为0。
某位置的元素被修改奇数次后值为1，被修改偶数次后值为0。
因此只需要求出某位置元素被修改的次数，即可得到该位置的数值。
每次修改是让连续的一段序列翻转，也就是选择数组的一段区间，将该区间中的元素取反（0变为1，1变为0）。
求某元素被修改的次数，就是求有多少个区间覆盖的该元素。
假想存在数组：cL，cR
$cL_i$ 表示区间左端点为i的区间数。
$cR_i$ 表示区间右端点为i的区间数。
$sumL_i$ ： $c L$ 的前缀和，即左端点L在[1,i]范围内的区间数
$sumR_i$ ： $c R$ 的前缀和，右端点R在[1,i]范围内的区间数
分别对cL、cR数组建立树状数组，借助树状数组可以在有单点修改的情况下，以 $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$ 的区间数量为 $sumL_x$ 。
右端点 $R < x$ 的区间数量为 $sumR_{x-1}$ 。
设包含x的区间的数量为 $ans_x$
有: $sumL_x = sumR_{x-1}+ans_x$
即 $ans_x = sumL_x-sumR_{x-1}$

具体做法：

如果需要将区间[l, r]中的元素取反，则存在一个区间 $[l, r]$ ，使 $cL_l$ 增加1， $cR_r$ 增加1。树状数组进行相应的单点修改操作。
如果需要查询第x元素的值，则通过 $ans_x=sumL_x-sumR_{x-1}$ 求出x被区间修改的次数 $ans_x$ ，如果 $ans_x$ 为奇数，第x元素值为1，否则第x元素值为0。

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

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

【题解代码】

解法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;
}

【题目链接】

【题目考点】

1. 树状数组

【解题思路】

解法1：树状数组

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

【题解代码】

解法1：树状数组

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

相关文章：

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

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