HBC53251UnitedinStormwind,组合数学,动态规划区间异或和异或区间最大值异或区间最小值题解（小w学会rmq算法）

惰性的成熟算法基础篇 2023-11-09 08:38:02 57 0

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

小w学会了RMQ算法，他现在可以求出一个给定数组某一段子区间的最大值，最小值，在这之前，他也学会了前缀和，并且他知道前缀和可以扩展到位运算求出区间异或和，现在你给了他一个长度大小为n的数组，为了考察小w写RMQ以及前缀异或和的正确性，你要求他求出该数组的某一个子区间，记该子区间的异或和为xorsum，记该子区间的最大值为max，记该子区间的最小值为min，你要求使得xorsum⊕max⊕min最大，其中⊕为位运算异或操作。

小w学会了RMQ算法，他现在可以求出一个给定数组某一段子区间的最大值，最小值。在这之前，他也学会了前缀和，并且他知道前缀和可以扩展到位运算求出区间异或和。现在你给了他一个长度大小为n的数组，为了考察小w写RMQ以及前缀异或和的正确性，你要求他求出该数组的某一个子区间，记该子区间的异或和为xorsum，记该子区间的最大值为max，记该子区间的最小值为min，你要求使得xorsum⊕max⊕min最大。其中⊕为位运算异或操作。