TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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命题