越秀区建设局网站,个人友情链接推广,wordpress浮动广告,青岛网站建设公司招聘似乎题解区并没有 cdq 套 cdq 的作法#xff0c;刚好今天讲了#xff0c;就来写一发。
题意与记号
题目讲的很清楚了。此方法并没有树状数组好想也没有其高效#xff0c;但能很方便扩展。下文记原序列为 ddd#xff0c;将每个点拆分成点与询问#xff0c;内部增加一个名为…似乎题解区并没有 cdq 套 cdq 的作法刚好今天讲了就来写一发。
题意与记号
题目讲的很清楚了。此方法并没有树状数组好想也没有其高效但能很方便扩展。下文记原序列为 ddd将每个点拆分成点与询问内部增加一个名为 ididid 的数据若其为 −1-1−1则是点否则是询问。
使用类 c 数组的书写方式否则角标太复杂实在不好看。下文先讲二维再讲三维。
二维偏序
先对 xxx 维排序再分治 yyy 维每一次分治中点为 midmidmid 的区间 [l,r)[l,r)[l,r)我们都能保证也必须保证 d[a].x≤d[b].xd[a].x\le d[b].xd[a].x≤d[b].xa∈[l,mid)a\in[l,mid)a∈[l,mid)b∈[mid,r)b\in[mid,r)b∈[mid,r)。
L{d[l],d[l1],d[l2],… } ↑R{d[mid],d[mid1],… } ↑
L\{d[l],d[l1],d[l2],\dots \} \\
\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \uparrow \\
R\{d[mid],d[mid1],\dots \} \\
\!\! \uparrow
L{d[l],d[l1],d[l2],…}↑R{d[mid],d[mid1],…}↑
我们对两边同时向后处理并非同步我们正在处理 d[a]d[a]d[a] 与 d[b]d[b]d[b]其中 d[a].id−1d[a].id-1d[a].id−1 与 d[b].id≠−1d[b].id\ne-1d[b].id−1其它情况不用考虑。
如果 d[a].y≤d[b].yd[a].y\le d[b].yd[a].y≤d[b].y由于分治LLL 与 RRR 内以 yyy 为关键字肯定是有序的所以 d[a′].y≤d[b′].yd[a].y\le d[b].yd[a′].y≤d[b′].ya′∈[l,a]a\in[l,a]a′∈[l,a]b′∈[b,r]b\in[b,r]b′∈[b,r]。
所以此时我们便可以记录 d[a]d[a]d[a] 的贡献这里是 111并将 d[a]d[a]d[a] 扔到归并排序的辅助数组里 a←a1a \leftarrow a1a←a1。
同理如果 d[a].yd[b].yd[a].y d[b].yd[a].yd[b].y我们直接由之前的贡献总和便可以计算答案并将 d[b]d[b]d[b] 扔到归并排序的辅助数组里b←b1b\leftarrow b1b←b1。
三维偏序
进入正题仿照上面的方法在第一次 cdq 内部每一层再执行另一种 cdqcdq2如果我们能保证 LLL 与 RRR 内部同时关于 xxx 与 yyy 有序就好了可是我们在分治的过程中必然会将 xxx 打乱如果有一种方法能告诉我们 xxx 曾经在哪边便能够解决这个问题。
也就是说我们只想要曾经xxx 维在左边点的对右边询问的做贡献。
为此我们扩展 ddd加入一个名为 tagtagtag 的数据表示在当层是在左边还是右边由于此时 yyy 早已有序仿照二维进行 cdq2。
解释见代码吧超详细的
namespace PB {node d[N]; // 存储当前处理的节点数组包含点和查询void solve(int l, int r) { // 处理区间 [l, r) 的 z 维偏序if (l r - 1) return; int mid (l r) 1; solve(l, mid), solve(mid, r); int a l, b mid, c l, sum 0; // sum 记录左边点的数量while (a mid || b r) { // 归并排序按 z 坐标合并if (b r || (a mid d[a].z d[b].z)) { // 左边还有元素且 z 更小或右边已空if (d[a].id -1 d[a].tag LEFT) // 如果是左边区间的一个点sum; tp[c] d[a]; } else { // 右边 z 更小或左边已空if (d[b].id ! -1 d[b].tag RIGHT) // 如果是右边区间的查询anst[d[b].id] sum; // 累加当前左边点的数量到查询结果tp[c] d[b]; }}copy(tp l, tp r, d l); // 将临时数组复制回原数组完成归并}
} // namespace PBnamespace PA {void solve(int l, int r) { // 处理区间 [l, r) 的 y 维偏序if (l r - 1) return; int mid (l r) 1; solve(l, mid), solve(mid, r); // 递归处理左半区间 [l, mid) 和右半区间 [mid, r)int a l, b mid, c l; // a, b 分别指向左右区间c 指向临时数组while (a mid || b r) { // 归并排序按 y 坐标合并if (b r || (a mid d[a].y d[b].y)) { // 左边还有元素且 y 更小或右边已空d[a].tag LEFT, tp[c] d[a]; // 标记为左区间} else { // 右边 y 更小或左边已空d[b].tag RIGHT, tp[c] d[b]; // 标记为右区间}}copy(tp l, tp r, d l); // 将临时数组复制回原数组完成 y 维归并copy(tp l, tp r, PB::d l); // 将排序后的数组复制到 PB 命名空间的 d 数组PB::solve(l, r); // 调用 PB 处理 z 维偏序}
} // namespace PA时间复杂度
PB 中一次处理长度为 nnn 的区间 O(n)nlognO(n)n\log nO(n)nlogn。
PA总O(∑i0lognT(n2i)×2i)O(nlog2n)O(\sum_{i0}^{\log n}T(\frac{n}{2^i})\times 2^i) O(n\log^2n)O(∑i0lognT(2in)×2i)O(nlog2n) 。
