【题目描述】题目来源CQOI 2006有一个 n 个元素的数组每个元素初始均为 0。有 m 条指令要么让其中一段连续序列数字反转——0 变 11 变 0操作 1要么询问某个元素的值操作 2。例如当 n20 时10 条指令如下操作回答操作后的数组1110N/A11111111110000000000261111111⎯⎯111100000000002120111111111100⎯⎯000000001512N/A11110000001100000000260111100⎯⎯000011000000002150111100000011000⎯⎯000001616N/A1111011111001111000011117N/A111101111111000010002121111101111111⎯⎯00001000261111101⎯⎯11111100001000【输入】第一行包含两个整数 n,m表示数组的长度和指令的条数以下 m 行每行的第一个数 t 表示操作的种类若 t1则接下来有两个数 L,R表示区间 [L,R] 的每个数均反转若 t2则接下来只有一个数 i表示询问的下标。【输出】每个操作 2 输出一行非 0 即 1表示每次操作 2 的回答。【输入样例】20 10 1 1 10 2 6 2 12 1 5 12 2 6 2 15 1 6 16 1 11 17 2 12 2 6【输出样例】1 0 0 0 1 1【提示】数据范围与提示对于 50% 的数据1≤n≤10^3,1≤m≤10^4 对于 100% 的数据1≤n≤10^5,1≤m≤5×10^5 保证 L≤R。一、 题目分析【题目大意】给定一个长度为n的数组初始所有元素均为0。系统会给出m条指令包含两种操作操作 1区间修改给定区间[L,R]将区间内的数字反转0 变 11 变 0。操作 2单点查询给定下标i查询当前位置的值。【数据范围】1≤n≤10^5,1≤m≤5×10^5。 极限情况下有50万次操作要求算法的时间复杂度必须严格控制在 O(MlogN) 级别否则必定超时。二、 思考过程反转操作的数学本质是什么在二进制的世界里状态的“反转”等价于“加上1然后对2取模”。也就是说如果一个位置被翻转了k次它的最终状态就是 k%2。如何高效处理“区间加法”如果在原数组上直接跑for循环时间复杂度是O(N)面对50 万次指令会直接崩溃。此时必须引入差分数组。 对于差分数组d给原数组区间[L,R] 加上 1等价于在差分数组上做两次单点修改d[L]1和d[R1]-1。如何高效处理“单点查询”原数组第i个位置的值等于差分数组d从1到i的前缀和。经过这三步推演问题被彻底剥去了伪装我们需要一个数据结构能够极速支持**“单点修改”和“查询前缀和”。这正是树状数组的绝对主场。三、 解题思路我们将原问题完全转换为树状数组的标准模板建树阶段由于初始数组全为0差分数组也全为0所以不需要任何预处理直接开一个初始值为0的树状数组即可。修改阶段遇到指令1读入L和R。调用update(L,1)和update(R1,-1)。查询阶段遇到指令2读入i。调用query(i)获取差分数组的前缀和即该位置被翻转的总次数然后输出query(i)%2即可。四、 算法设计lowbit函数x(-x)用于快速定位树状数组的管辖区间。update函数通过xlowbit(x)向上攀升更新所有包含该单点的父节点。query函数通过x-lowbit(x)向下聚拢快速累加出前缀和。IO优化使用cin.tie(0)解除流绑定确保在5×10^5级别的数据输入下不被卡常。五、 时空复杂度分析时间复杂度树状数组的每次update和query都是严格的O(logN)。共有M条指令总体时间复杂度为O(MlogN)。在 10^5 级别的数据下最大计算量仅千万级别100ms 内即可瞬间跑完。空间复杂度只需开辟一个大小为N1的树状数组c[]空间复杂度为O(N)。极致轻量。六、 易错点总结数组越界防范当反转的区间到达数组最右端Rn时update(R1,-1)会试图访问 n1 的位置。但由于update的内部循环条件是while(xn)参数n1传进去后会直接跳过循环天然免疫了越界报错。取模负数陷阱C中负数取模依然是负数。本题中由于是累加区间覆盖次数前缀和绝对不可能为负所以写update(R1,-1)是安全的。但更严谨的竞赛技巧是既然只关心奇偶性加1和减1效果相同可以直接写成update(R1,1)从根源上杜绝负数的出现。滥用线段树本题用线段树完全可以做但线段树常数极大容易在极限数据下被卡。能用树状数组解决的差分问题绝不用线段树。七、 题解本题是利用“差分思想”将区间操作降维的极佳例题。通过将“区间反转”转化为“区间加法”再利用差分将其转化为“单点修改”最终用常数极小、代码极短的树状数组完成了对暴力算法的降维打击。八、 完整代码//区间修改 单点查询 翻转可以理解为1然后对2取模 #include iostream using namespace std; int n,m; int a[500010];//原数组 每个元素均为0 int d[500010];//差分数组 int c[500010];//树状数组 //返回x二进制表示下最低位的1所代表的整数 int lowbit(int x){ return x(-x); } //树状数组更新操作 void update(int x,int k){ //向上更新所有包含x的大区间 while(xn){ c[x]k; xlowbit(x); } } //树状数组查询 int query(int x){ int ret0;//记录前缀和 while(x0){ retc[x]; x-lowbit(x); } //核心总翻转次数对2取模得出最终的0或1 return ret%2; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; for(int i1;in;i){ a[i]0;//原数组 每个元素均为0 d[i]a[i]-a[i-1];//差分数组 update(i,d[i]);//更新树状数组 } //m组指令 while(m--){ int t; cint; if(t1){//l-r区间翻转 int l,r; cinlr; update(l,1); update(r1,-1); } else{//查询 int i; cini; coutquery(i)\n; } } return 0; }
简单题（信息学奥赛一本通- P1539）
【题目描述】题目来源CQOI 2006有一个 n 个元素的数组每个元素初始均为 0。有 m 条指令要么让其中一段连续序列数字反转——0 变 11 变 0操作 1要么询问某个元素的值操作 2。例如当 n20 时10 条指令如下操作回答操作后的数组1110N/A11111111110000000000261111111⎯⎯111100000000002120111111111100⎯⎯000000001512N/A11110000001100000000260111100⎯⎯000011000000002150111100000011000⎯⎯000001616N/A1111011111001111000011117N/A111101111111000010002121111101111111⎯⎯00001000261111101⎯⎯11111100001000【输入】第一行包含两个整数 n,m表示数组的长度和指令的条数以下 m 行每行的第一个数 t 表示操作的种类若 t1则接下来有两个数 L,R表示区间 [L,R] 的每个数均反转若 t2则接下来只有一个数 i表示询问的下标。【输出】每个操作 2 输出一行非 0 即 1表示每次操作 2 的回答。【输入样例】20 10 1 1 10 2 6 2 12 1 5 12 2 6 2 15 1 6 16 1 11 17 2 12 2 6【输出样例】1 0 0 0 1 1【提示】数据范围与提示对于 50% 的数据1≤n≤10^3,1≤m≤10^4 对于 100% 的数据1≤n≤10^5,1≤m≤5×10^5 保证 L≤R。一、 题目分析【题目大意】给定一个长度为n的数组初始所有元素均为0。系统会给出m条指令包含两种操作操作 1区间修改给定区间[L,R]将区间内的数字反转0 变 11 变 0。操作 2单点查询给定下标i查询当前位置的值。【数据范围】1≤n≤10^5,1≤m≤5×10^5。 极限情况下有50万次操作要求算法的时间复杂度必须严格控制在 O(MlogN) 级别否则必定超时。二、 思考过程反转操作的数学本质是什么在二进制的世界里状态的“反转”等价于“加上1然后对2取模”。也就是说如果一个位置被翻转了k次它的最终状态就是 k%2。如何高效处理“区间加法”如果在原数组上直接跑for循环时间复杂度是O(N)面对50 万次指令会直接崩溃。此时必须引入差分数组。 对于差分数组d给原数组区间[L,R] 加上 1等价于在差分数组上做两次单点修改d[L]1和d[R1]-1。如何高效处理“单点查询”原数组第i个位置的值等于差分数组d从1到i的前缀和。经过这三步推演问题被彻底剥去了伪装我们需要一个数据结构能够极速支持**“单点修改”和“查询前缀和”。这正是树状数组的绝对主场。三、 解题思路我们将原问题完全转换为树状数组的标准模板建树阶段由于初始数组全为0差分数组也全为0所以不需要任何预处理直接开一个初始值为0的树状数组即可。修改阶段遇到指令1读入L和R。调用update(L,1)和update(R1,-1)。查询阶段遇到指令2读入i。调用query(i)获取差分数组的前缀和即该位置被翻转的总次数然后输出query(i)%2即可。四、 算法设计lowbit函数x(-x)用于快速定位树状数组的管辖区间。update函数通过xlowbit(x)向上攀升更新所有包含该单点的父节点。query函数通过x-lowbit(x)向下聚拢快速累加出前缀和。IO优化使用cin.tie(0)解除流绑定确保在5×10^5级别的数据输入下不被卡常。五、 时空复杂度分析时间复杂度树状数组的每次update和query都是严格的O(logN)。共有M条指令总体时间复杂度为O(MlogN)。在 10^5 级别的数据下最大计算量仅千万级别100ms 内即可瞬间跑完。空间复杂度只需开辟一个大小为N1的树状数组c[]空间复杂度为O(N)。极致轻量。六、 易错点总结数组越界防范当反转的区间到达数组最右端Rn时update(R1,-1)会试图访问 n1 的位置。但由于update的内部循环条件是while(xn)参数n1传进去后会直接跳过循环天然免疫了越界报错。取模负数陷阱C中负数取模依然是负数。本题中由于是累加区间覆盖次数前缀和绝对不可能为负所以写update(R1,-1)是安全的。但更严谨的竞赛技巧是既然只关心奇偶性加1和减1效果相同可以直接写成update(R1,1)从根源上杜绝负数的出现。滥用线段树本题用线段树完全可以做但线段树常数极大容易在极限数据下被卡。能用树状数组解决的差分问题绝不用线段树。七、 题解本题是利用“差分思想”将区间操作降维的极佳例题。通过将“区间反转”转化为“区间加法”再利用差分将其转化为“单点修改”最终用常数极小、代码极短的树状数组完成了对暴力算法的降维打击。八、 完整代码//区间修改 单点查询 翻转可以理解为1然后对2取模 #include iostream using namespace std; int n,m; int a[500010];//原数组 每个元素均为0 int d[500010];//差分数组 int c[500010];//树状数组 //返回x二进制表示下最低位的1所代表的整数 int lowbit(int x){ return x(-x); } //树状数组更新操作 void update(int x,int k){ //向上更新所有包含x的大区间 while(xn){ c[x]k; xlowbit(x); } } //树状数组查询 int query(int x){ int ret0;//记录前缀和 while(x0){ retc[x]; x-lowbit(x); } //核心总翻转次数对2取模得出最终的0或1 return ret%2; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; for(int i1;in;i){ a[i]0;//原数组 每个元素均为0 d[i]a[i]-a[i-1];//差分数组 update(i,d[i]);//更新树状数组 } //m组指令 while(m--){ int t; cint; if(t1){//l-r区间翻转 int l,r; cinlr; update(l,1); update(r1,-1); } else{//查询 int i; cini; coutquery(i)\n; } } return 0; }
