首页 > 试题广场 >

无效位置

[编程题]无效位置

给一个1-base数组{a}，有N次操作，每次操作会使一个位置无效。一个区间的权值定义为这个区间里选出一些数的异或和的最大值。求在每次操作前，所有不包含无效位置的区间的权值的最大值。

第一行读入一个正整数(1 <= n <= 10⁵)
第二行读入n个正整数，第i个表示a[i](0<= a[i] <= 10⁹)
第三行读入n个正整数，第i个表示x[i]即第i次操作的位置，保证x[i]互不相同。

输出n行答案

示例1

输入

10
169 816 709 896 58 490 97 254 99 796 
4 2 3 10 5 6 1 8 9 7

算法知识视频讲解

-符拉迪沃斯托克-

发表于 2021-08-20 20:01:41

如果没有修改，这个题就是个线性基板子题对吧。再看加上修改之后怎么整。我们发现，对于任意一种已经确定数字的情况，只要线性基建好了，答案可以搞出来。那么问题就是怎么动态维护线性基。啥？动态维护？？不存在的！我才不告诉你我不会写那玩意因为只有删除操作，所以顺序颠倒就是一个一个加入数字。也就是离展开全文

Roark

发表于 2019-07-23 15:13:27

正好打比赛遇到了就顺便试一试牛客的博客功能~感觉这个风格还是比较舒服的~ 线性基用来处理异或和问题，可以log时间判断一段区间内异或和的最大最小值以及是否可以异或出某个数。线性基所用到的思想类似于可以用10个数来表示0~1023 我们用一个数组a表示线性基，数组的展开全文

并查集

上传者：牛客301599号

难度：

0条回答 0收藏 13浏览

查看代码

无效位置

扫一扫，把题目装进口袋