TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5412
  • 题目
  • P5412【继续欢乐】赚钱的游戏·异世界
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    问题描述

    \(n\) 堆石子排成一排,每堆石子的数量都是非负整数。

    每次操作可以选择相邻的两堆石子合并,在这个异世界里面,如果这两堆石子的数量分别是 \(x,y\) ,则合并之后可以得到 \(x\ \text{AND}\ y\) 元人民币,合并成一堆石子的数量是 \(x\ \text{XOR}\ y\) ,然后放回原位。进行 \(n-1\) 次操作之后所有石子都合并成一堆。所有操作获得的总人民币,也是每次得到的人民币异或后的结果。

    你很优秀,总是按照最终获得人民币数量最多的策略进行合并。

    异世界很不稳定,每堆石子的数量可能随时发生变化。而且有些时候你只能选择中间连续的一段石子进行合并,你需要快速回答某个时刻假如把从第 \(L\) 堆石子到第 \(R\) 堆石子合并成一堆,最多能获得多少人民币。

    输入格式

    输入共 \(m+2\) 行。 第一行两个整数 \(n,m\),表示石子的堆数和事件的次数。 第二行 \(n\) 个非负整数,表示初始状态下每堆石子的数量。 接下来 \(m\) 行,每行三个整数 \(k,a,b\)\(k=1\) 表示第 \(a\) 堆石子变成了 \(b\) 个, \(k=2\) 表示询问假如把从第 \(a\) 堆到第 \(b\) 堆石子合并成一堆,最多能获得多少人民币。

    输出格式

    每次 \(k=2\) 的事件输出一行,包含一个数,表示最多能获得的人民币。

    样例输入

    6 6
    4 4 1 2 7 0
    2 1 6
    2 1 3
    1 3 7
    1 6 0
    2 1 3
    2 3 5

    样例输出

    7
    4
    4
    7

    提示

    $1\leq n\leq 105, 1\leq m\leq 105, 0\leq \text{每堆石子数}\leq 10^9$


    来源  感谢nodgd命题