#P5312. 冒险

    ID: 4325 传统题 1000ms 512MiB 尝试: 527 已通过: 161 难度: 8 上传者: 标签>CF2400提高+/省选-Segment Tree Beats懒标记线段树标记复合势能分析By佚名上传

冒险

Description

Kaiser终于成为冒险协会的一员。这次,冒险协会派他去冒险。他来到一处古墓,却被大门上的守护神挡住了去路。守护神给出了一个问题,只有答对了问题才能进入古墓。守护神给出了一个自然数序列 aa,并要求你在序列上执行以下三种操作:

  1. 给定 l,r,xl, r, x,将序列第 ll 到第 rr 之间的所有数都执行按位与(AND)操作,操作数为 xx。
  2. 给定 l,r,xl, r, x,将序列第 ll 到第 rr 之间的所有数都执行按位或(OR)操作,操作数为 xx。
  3. 给定 l,rl, r,查询序列第 ll 到第 rr 之间的最大值。

Input Format

第一行包含两个整数 nn 和 mm,分别表示序列的长度和操作的数量。

第二行包含 nn 个整数,表示序列 aa。

接下来 mm 行,每行描述一个操作:

  • 1:给出 l,r,xl, r, x,将序列第 ll 到第 rr 之间的所有数都执行 AND 操作,操作数为 xx。
  • 2:给出 l,r,xl, r, x,将序列第 ll 到第 rr 之间的所有数都执行 OR 操作,操作数为 xx。
  • 3:给出 l,rl, r,询问序列第 ll 到第 rr 之间的最大值。

约束条件:

  • 2≤n≤2×1052 \leq n \leq 2 \times 10^5
  • 2≤m≤2×1052 \leq m \leq 2 \times 10^5
  • 0≤ai<2200 \leq a_i < 2^{20}
  • 1≤l≤r≤n1\le l\le r\le n,区间包括两个端点。
  • 本站评测的所有按位与、按位或操作数都满足 0≤x<2200\le x<2^{20}。

Output Format

对于每个第三类询问,输出一个数字,即对应区间的最大值。

Example

3 5
9 19 0
3 2 3
2 3 3 18
1 2 2 10
3 1 2
1 1 3 11
19
9

题目来源