首页 > 小 Q 与彼岸花
开通博客写题解
头像 qingshan_12
发表于 2021-04-24 19:11:04
题意：查询m次，每次输出区间[l, r]内两个数的最大异或值。因为是区间内的最大值求解问题，可以通过区间dp来进行分析。区间[l,r]内的最大值可以由区间端点l, r, 或者区间[l + 1, r] 和 [l, r - 1] 内的最大值取出。例如： 有三个数 1， 2， 3 求区间[1, 3]内的最 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 牛客345829520号
发表于 2021-04-24 11:54:34
小 Q 与彼岸花题意给你n个数，m组询问，让你求出每组询问中在区间[L,R]上两个数最大的异或值。思路昨天晚上以为时间复杂度为5e5，一直想不到思路，就没写出来。今天早上又看了一眼数据范围，是5e3...我们可以把所有的情况都预处理出来。我们可以用两层循环来枚举每一个区间[i,j].比如当前的区间是 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 昵称很长很长真是太好了
发表于 2021-04-26 19:08:00
题意：题解：因为这个题目是弱化以后的，正常的范围是5e4 . 看了官方题解去学习了一波可持久化01trie然后回来把这个题补完。 可持久数据结构其实就是我们的数据结构的内容会不断发生变化，而我们还要查询以前的历史版本，比如某个区间的情况。 听名字可以听出来，可持久化01trie跟可持久化线段树差不 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”