Codeforces E 665 Beautiful Subarrays (字典树上分治)

给出n个数字,求连续子序列异或和>=k的个数。

不妨先预处理出前缀的异或和,那么任意一段连续子序列的异或和等于前后两个位置前缀异或和的异或,那么问题可以转化成区间任意两个数字异或>=k的对数。我们不妨枚举连续子序列的右端点,然后去找左端点匹配的个数,找匹配的个数可以在字典树上分治。

 

LEAVE A COMMENT