DTOJ4349. 「十二省联考 2019」异或粽子

本文主要是介绍DTOJ4349. 「十二省联考 2019」异或粽子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
有一个长度为n的数列，每次可以取一段区间的异或和，求前k大的取值之和。
n<=5e5,k<=2e5
题解：
考场：显然一段区间的异或和应转化为两个前缀异或和的异或值，于是问题转为给n+1个数，两两之间异或和前k大的和。对于异或和的问题考虑trie树，每次贪心取不同的两边，然后一直没有注意到k和n不是一个数量级别，一直把k当做n*n的级别考虑，就凉了。（甚至暴力的k开的都是long long……）
正解：发现k和n不是一个数量级别，当然要先考虑k了！考虑一个个取当前的最大异或值，为了不重不漏，显然是枚举每个右端点，找前面最大的和它的异或值，但这样找完一个值后要怎么找下一个呢？考虑用优先队列维护动态维护最大值，因为所有右端点和前面的值的异或值就构成了所有可能的值，故对于一个最大值的右端点，取完值后，就找前面和它异或值的次大值，扔进堆里，即堆里的每个元素记下它的右端点。找与前面的数异或的k大值，用可持久化trie树即可。
反思：最近总是死于看题，前两天是题意自己yy错了，然后今天又没有注意到题目的切入口，以后看题要多注意了。

这篇关于DTOJ4349. 「十二省联考 2019」异或粽子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---