Readme

2736.Maximum-Sum-Queries

如果我们将每个query独立地去做，需要暴力地扫所有的nums。一种常见的应对思路是Off-line Querying，将query进行某种意义上的排序，通常先解决的query会对后面的query帮助。但是这个思路似乎对本题没有帮助。比如说，将query按照x从大到小排序，随着query的逐一解答，我们可用的nums也会逐渐增多，但是并不能帮我们方便地兼顾“满足关于y的约束”以及“取最大sum”。

但是此题还有另外一种对偶的思路，将nums进行某种意义上的排序。我们发现，对于sum最大的num，任何满足x和y约束的所有query，必然会取该sum作为答案，既然找到了答案，那么就可以从待求的query的集合中删除。为了容易找到这些满足约束的query，我们可以将所有query先按照x排序，再按照y排序，构造二层的数据结构。这样，在第一层，任何x小于nums1[j]的query都会入选；然后在对应的第二层，任何y小于nums2[j]的query都可以被选中，标记它们的答案是sum。可以发现，这些被选中的query是分块连续的，我们可以很方便地删除。

同理，我们再处理sum为次大的num，删除所有答案是它的query。以此类推。

分析时间复杂度：我们令num的个数是m，query的个数是n。我们对于每个num，都会在query集合里删除答案对应是num的query。注意在第二层，每个query只会被访问和删除一次。所以代码核心的时间复杂度是M+N. 不过预处理有一个对num和query分别排序的过程。

注意，为了提高效率，如果某个二层集合里的query被删空了，务必把它们的一层指针也移除。