#P6921. 神犇

    ID: 6752 传统题 1500ms 1024MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>数据结构贪心字符串队列CF2500字典树模拟

神犇

Problem B. 神犇(imbalance)

时间限制:2秒;内存限制:256 MiB。

众所周知,蒟蒻总是崇拜神犇。在 NFLS 里,有 nn 个蒟蒻,编号为 1,2,...,n1,2,...,n。lqs 是其中的一员。他们每个人都有一个崇拜的神犇,每个人崇拜的神犇都是 FizzyDavid,Ohweonfire,diamond_duke 中的一个。编号为 ii 个蒟蒻对他崇拜的神犇的崇拜度为 AiA_{i}。

wzy 是 NFLS 的另外一位神犇,他也希望有蒟蒻来崇拜他。现在 wzy 想要选择编号为一个区间的蒟蒻,使得他们崇拜他。对于编号为 [l,r][l,r] 的蒟蒻来说,如果存在两个神犇,崇拜他们的蒟蒻个数相同 (可能为 00),那么这个区间的不平衡度为 00。否则这个区间的不平衡度为这个区间中所有蒟蒻对他们崇拜的神犇的崇拜度的异或和,即 Al⊕Al+1⊕⋯⊕ArA_{l}\oplus A_{l+1}\oplus \cdots \oplus A_{r},其中 ⊕\oplus 是异或操作。

现在 wzy 想知道对于所有的 x(1≤x≤n)x(1\le x\le n),以 xx 为右端点的区间的不平衡度的最大值,因为不平衡度越大,wzy 越好下手。神犇总是日理万机,所以他没时间做这个。因为你是 wzy 的粉丝,所以他把这个任务交给了你。

输入格式

第一行两个整数 n,optn,opt,表示蒟蒻的个数,若 opt=0opt=0,则不强制在线,否则表示强制在线。如果 opt=2opt=2 则表示一种特殊的部分分,请见“约束”。

第二行为 nn 个用空格分隔的整数 p1,p2,…,pnp_1,p_2,\ldots,p_n;解密后每个数是 0,1,20,1,2 之一。表示第 ii 个蒟蒻崇拜的神犇,00 表示 FizzyDavid,11 表示 Ohweonfire,22 表示 diamond_duke。

如果 opt≠0opt\ne0,记上面这 nn 个数的序列为 p1,p2,⋯ ,pnp_{1},p_{2},\cdots ,p_{n},那么真实的数字=(lastans⊕pi)mod3=(lastans\oplus p_{i})mod3, 否则输入的 pip_{i} 就是真实的数字。

第三行为 nn 个数 A1,A2,⋯ ,AnA_{1},A_{2},\cdots ,A_{n}。其意义如题。

如果 opt≠0opt\ne0,那么真实的数字 = lastans ⊕AiA_{i},否则输入的 AiA_{i} 就是真实的数字,其中,处理第 ii 个位置时,lastanslastans 为第 i−1i-1 个位置的答案,初始为 00;两类输入均使用这个 lastanslastans 解密。范围限制针对解密后的值。

输出格式

输出共一行,有 nn 个数,第 ii 个数表示以 ii 为右端点的区间的不平衡度的最大值。

样例

样例输入

8 0
0 1 2 2 1 1 0 0
2 3 7 1 4 5 3 2

样例输出

0 0 0 5 2 6 7 4

样例输入

10 0
0 0 0 0 0 0 0 0 0 0
1 2 4 8 16 32 64 128 256 512

样例输出

0 0 0 0 0 0 0 0 0 0

样例解释

样例 11 中,选择的区间分别为 [1,1],[2,2],[3,3],[2,4],[3,5],[1,6],[2,7],[6,8][1,1],[2,2],[3,3],[2,4],[3,5],[1,6],[2,7],[6,8]。 样例 22 是 FizzyDavid 粉丝群。

约束

对于 100%100\% 的数据,n≤300000n\le300000,Ai≤109A_i\le10^9(真实值)。

子任务 分数 特殊限制
1 20 n≤2000n\le2000
2 解密后只含 0,10,1 两种类型;该档数据均满足 opt=2opt=2
3 opt=0opt=0
4 n≤105n\le10^5
5 无特殊限制