#3733. 序列覆盖与区间异或

序列覆盖与区间异或

题目描述

给定一个长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\dots,a_n,以及 mm 次操作。操作分为三种:

  • 1 l r x:将区间 [l,r][l,r] 内的每个数 aia_i 修改为 ai⊕xa_i \oplus x,其中 ⊕\oplus 表示按位异或。
  • 2 l r:查询区间 [l,r][l,r] 内所有数的按位异或和。
  • 3 l r:查询区间 [l,r][l,r] 内所有数的按位或和。

请你依次处理所有操作,并输出每次查询的结果。

输入格式

第一行包含两个整数 n,mn,m,分别表示序列长度和操作次数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n。

接下来 mm 行,每行描述一次操作,格式如下:

  • 1 l r x:区间异或修改;
  • 2 l r:查询区间异或和;
  • 3 l r:查询区间按位或和。

保证 1≤l≤r≤n1 \le l \le r \le n。

输出格式

对于每个类型为 22 或 33 的操作,输出一行一个整数,表示查询结果。

样例

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≤n,m≤2×1051 \le n,m \le 2 \times 10^5
  • 0≤ai,x<2300 \le a_i,x < 2^{30}

样例说明

样例 1 中:

  • 初始序列为 [1,2,3][1,2,3]。
  • 查询 [1,3][1,3] 的异或和:1⊕2⊕3=01 \oplus 2 \oplus 3 = 0。
  • 对 [1,2][1,2] ��或 11,序列变为 [0,3,3][0,3,3]。
  • 查询 [1,3][1,3] 的异或和:0⊕3⊕3=00 \oplus 3 \oplus 3 = 0。
  • 查询 [1,3][1,3] 的按位或和:0∣3∣3=30 \mid 3 \mid 3 = 3。

样例 2 中:

  • 初始序列为 [5,1,4,2][5,1,4,2]。
  • 对 [2,3][2,3] 异或 66,序列变为 [5,7,2,2][5,7,2,2]。
  • 查询 [1,4][1,4] 的异或和:5⊕7⊕2⊕2=25 \oplus 7 \oplus 2 \oplus 2 = 2。
  • 查询 [2,4][2,4] 的按位或和:7∣2∣2=77 \mid 2 \mid 2 = 7。
  • 对 [1,4][1,4] 异或 33,序列变为 [6,4,1,1][6,4,1,1]。
  • 查询 [1,2][1,2] 的异或和:6⊕4=26 \oplus 4 = 2。

解析

解题思路

本题要求支持区间异或修改、区间异或和查询、区间按位或和查询。由于异或修改会影响每个数的每一位,我们可以按位维护信息。

对于每个线段树节点,维护:

  • xr:该区间所有数的异或和;
  • cnt[b]:该区间内第 bb 位为 1 的数的个数(0≤b<300 \le b < 30);
  • len:区间长度。

当对整个区间异或 xx 时,对于 xx 中为 1 的每一位 bb,该区间��第 bb 位为 1 的个数变为 len - cnt[b],同时异或和 xr 的第 bb 位会翻转。我们可以用懒标记 lazy 记录待下传的异或值,下传时对子节点执行同样的变换。

区间异或和查询直接合并左右子树的 xr 即可。区间按位或和查询则检查区间内每一位是否存在至少一个 1,即 cnt[b] > 0,将这些位组合起来即为答案。

算法选择理由

若暴力修改和查询,单次操作最坏 O(n)O(n),总复杂度 O(nm)O(nm),无法承受 2×1052 \times 10^5 的数据。线段树配合懒标记可以将每次操作降到 O(30log⁡n)O(30 \log n)。按位维护 cnt 使得异或修改可以整体处理,无需逐元素修改。

复杂度分析

  • 建树:O(30n)O(30n);
  • 每次修改:访问 O(log⁡n)O(\log n) 个节点,每个节点处理 30 位,复杂度 O(30log⁡n)O(30 \log n);
  • 每次查询:异或和查询 O(log⁡n)O(\log n),或和查询需要合并 30 位信息,复杂度 O(30log⁡n)O(30 \log n);
  • 空间复杂度:O(30n)O(30n)。

总时间复杂度 O((n+m)⋅30log⁡n)O((n+m) \cdot 30 \log n),在 n,m≤2×105n,m \le 2 \times 10^5 时可以通过。

来源

AI 生成 · 云端大模型(域):deepseek-chat · NOI/NOI+/CTS · 线段树