前言
为啥要用分块呀,cdq 分治真好写!
前置知识:三维偏序模版。
思路
记 \(s_{i, j}\) 表示:对角坐标为 \((-\infty, -\infty)\) 到 \((i, j)\) 的矩形内的点权之和。
那么类似二维前缀和:对角坐标为 \((x1,y1)\) 到 \((x2, y2)\) 的矩形内的点权之和,可以表示成 \(s_{x2,y2} -s_{x1-1,y2} - s_{x2,y1-1} + s_{x1-1,y1-1}\)。
这样,我们发现,每个询问可以拆成四个点,用这四个点的答案即可求出询问。我们称这个拆出来的点叫查询点。
考虑转化为偏序问题(这样能用 cdq 求解)。
对于一个属性,记录 \(a,b\) 表示 \(s_{i,j}\) 中的 \(i\) 与 \(j\)。为了方便,再记录 \(c\) 表示:当前属性是普通点还是查询点。
那么,若属性 \(X\) 可以计算 \(Y\) 的贡献入内,需要满足:
\(\begin{cases}Y_a \le X_a\\Y_b \le X_b\\Y_c < X_c\end{cases}\)
前面两个限制表示下标要包含在矩形内才行。第三个限制表示 \(X\) 是查询点 且 \(Y\)。
标签:偏序,y2,题解,矩形,x2,y1,x1,P3755 From: https://www.cnblogs.com/liangbowen/p/16798839.html