7574 -- 【6.05模拟】数据结构

分块

二次离线回滚莫队

cdq分治+扫描线

题目限制太多，考虑先消去\(y\)的限制，很容易想到将点分成\(y\le mid\)和\(y>mid\)两部分，此时上下两部分可以分开统计最大值

但是如果直接将询问扔进去又会变成\(O(nQlogn)\)的，考虑这个过程能否优化

重要性质：Red和Blue的最大值至少会被取到一个

这个易证，当\(v^{max}_{red}\)和\(v^{max}_{blue}\)出现在同一贡献区间（\(x_r<L\ \&\ x_b>R\) 或相反），那么答案肯定是\(v^{max}_{red}+v^{max}_{blue}\)；如果在不同区间，那么答案就是\(max(v^{max}_{red}+v_b,v^{max}_{blue}+v_r)\)，找别的数顶掉最大值一定不优

说明答案一定有最大值，我们对于两部分分别于对面的最大值拼凑，就能得到对答案有贡献的点对，为\(O(nlogn)\)级别的

最后就是对询问的回答了，对\(L,R\)求\(x_r<L\ \&\ x_b>R\)（和另一个）的点对的最大权值，发现这就是一个两维为\(x_r,x_b\)的二维数点，而且贴边界，很容易扫描线+树状数组做出来

至此整道题就解决了，时间复杂度\(O((n+Q)\log n)\)

总结

方法真的很多，建议学了之后回去试试别的做法

做法3中，如果矩形不贴边界，是否可做？

整出来了，但是莫队link