#3733. 序列覆盖与区间异或
序列覆盖与区间异或
题目描述
给定一个长度为 的整数序列 ,以及 次操作。操作分为三种:
1 l r x:将区间 内的每个数 修改为 ,其中 表示按位异或。2 l r:查询区间 内所有数的按位异或和。3 l r:查询区间 内所有数的按位或和。
请你依次处理所有操作,并输出每次查询的结果。
输入格式
第一行包含两个整数 ,分别表示序列长度和操作次数。
第二行包含 个整数 。
接下来 行,每行描述一次操作,格式如下:
1 l r x:区间异或修改;2 l r:查询区间异或和;3 l r:查询区间按位或和。
保证 。
输出格式
对于每个类型为 或 的操作,输出一行一个整数,表示查询结果。
样例
3 5
1 2 3
2 1 3
1 1 2 1
2 1 3
3 1 3
2 2 3
0
0
3
0
4 6
5 1 4 2
1 2 3 6
2 1 4
3 2 4
1 1 4 3
2 1 2
3 1 4
2
7
2
7
说明/提示
数据范围
样例说明
样例 1 中:
- 初始序列为 。
- 查询 的异或和:。
- 对 ��或 ,序列变为 。
- 查询 的异或和:。
- 查询 的按位或和:。
样例 2 中:
- 初始序列为 。
- 对 异或 ,序列变为 。
- 查询 的异或和:。
- 查询 的按位或和:。
- 对 异或 ,序列变为 。
- 查询 的异或和:。
解析
解题思路
本题要求支持区间异或修改、区间异或和查询、区间按位或和查询。由于异或修改会影响每个数的每一位,我们可以按位维护信息。
对于每个线段树节点,维护:
xr:该区间所有数的异或和;cnt[b]:该区间内第 位为 1 的数的个数();len:区间长度。
当对整个区间异或 时,对于 中为 1 的每一位 ,该区间��第 位为 1 的个数变为 len - cnt[b],同时异或和 xr 的第 位会翻转。我们可以用懒标记 lazy 记录待下传的异或值,下传时对子节点执行同样的变换。
区间异或和查询直接合并左右子树的 xr 即可。区间按位或和查询则检查区间内每一位是否存在至少一个 1,即 cnt[b] > 0,将这些位组合起来即为答案。
算法选择理由
若暴力修改和查询,单次操作最坏 ,总复杂度 ,无法承受 的数据。线段树配合懒标记可以将每次操作降到 。按位维护 cnt 使得异或修改可以整体处理,无需逐元素修改。
复杂度分析
- 建树:;
- 每次修改:访问 个节点,每个节点处理 30 位,复杂度 ;
- 每次查询:异或和查询 ,或和查询需要合并 30 位信息,复杂度 ;
- 空间复杂度:。
总时间复杂度 ,在 时可以通过。
来源
AI 生成 · 云端大模型(域):deepseek-chat · NOI/NOI+/CTS · 线段树