Description

给定平面上的 $n$ 个点 $(i,p_i)$，每个点有权值 $w_i$。保证 $p_i$ 为一个 $n$ 阶排列。

再给你 $m$ 个矩形 $(l_x,r_x,l_y,r_y)$。

$q$ 次查询 $(l,r)$，求出第 $l\sim r$ 个矩形的并中的点权和。

Limitations

$1\le n,m\le 10^5$

$1\le q\le 10^6$

$1\le a_i\le 10^4$

$4\text{s},128\text{MB}$

Solution

视 $n,m$ 同阶。

显然 $[l,r]$ 的矩形并就是在平面上依次将第 $l\sim r$ 个矩形覆盖后，被覆盖的区域。

那么可以想到 P8512，考虑类似于那题的做法。对时间轴做扫描线，那么需要一个 DS 支持：

• 给一块矩形覆盖上颜色 $i$。
• 求颜色在 $[l,r]$ 间的区域的点权和。

维护当前每个矩形内的贡献 $f_i$。对这 $n$ 个点建 KDT。对于覆盖，将矩形拆成 KDT 上的 $O(\sqrt n)$ 个节点。对每个节点 $u$，先把它子树内的 $\text{tag}$ 清空（这里的复杂度可以摊还），再给这个节点打上 $\text{tag}$，并在 $f$ 上做对应修改。查询就直接查 $f$ 的区间和。

现在对于 $f$，有 $O(n\sqrt n)$ 次单点加，$O(q)$ 次区间查，$O(1)-O(\sqrt n)$ 分块即可。

这样就得到一个 $O((n+q)\sqrt n)$ 的做法，可以过。