P4735 最大异或和

    • 785通过
    • 3.1K提交
  • 题目提供者 yyy2015c01 嘤嘤嘤
  • 评测方式 云端评测
  • 标签 前缀和 可持久化 字典树,Trie树
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一个非负整数序列$\{a\}$,初始长度为$N$。

    有M个操作,有以下两种操作类型:

    1. A x:添加操作,表示在序列末尾添加一个数$x$,序列的长度$N+1$。
    2. Q l r x:询问操作,你需要找到一个位置$p$,满足$l \le p \le r$,使得: $ a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x$ 最大,输出最大是多少。

    输入输出格式

    输入格式:

    第一行包含两个整数 $N,M$,含义如问题描述所示。
    第二行包含 $N$个非负整数,表示初始的序列$ A$ 。
    接下来 $M$行,每行描述一个操作,格式如题面所述。

    输出格式:

    假设询问操作有 $T$ 个,则输出应该有 $T$ 行,每行一个整数表示询问的答案。

    输入输出样例

    输入样例#1: 复制
    5  5
    2  6 4 3 6
    A 1 
    Q 3 5 4 
    A 4
    Q 5 7 0 
    Q 3 6 6 
    输出样例#1: 复制
    4
    5
    6

    说明

    对于测试点 $1-2$,$N,M \le 5$。
    对于测试点 $3-7$,$N,M \le 80000$。
    对于测试点 $8-10$,$N,M \le 300000$。
    其中测试点 $1, 3, 5, 7, 9$保证没有修改操作。
    $0 \le a[i] \le 10^7$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。