警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「算法」CDQ 分治和整体二分 - 离线 (TBC)

简介

CDQ 分治是分治的一种,思想是对于操作是多维的问题,分治其中一维,并对右段处理左段的贡献,递归地计算答案。[思维已崩坏]

CDQ 分治

使用前提

  • 显然必须可以离线
  • 询问没有后效性

流程

  • 分治区间 \([l, r)\)
    1. 将区间分为 \([l, mid)\)\([mid, r)\) 两部分
    2. 分治区间 \([l, mid)\)
    3. 分治区间 \([mid, r)\)
    4. 按照分治维度的大小关系,用双指针处理出左段对右段每个操作的贡献
    5. 在 4 的同时以分治维度作为关键字排序

具体实现

实现方式非常臭。所以:

来自基金会信息安全管理系统的通知

以下文件包含致命信息危害,因此,访问此文件的人员需具有不小于 14.5 的认知阻值(CRV),若您未通过自动 CRV 验证,请保持冷静且不要活动,您所在机房的医护人员 蒟蒻 tiger0132 将即刻与你同在。

整体二分 (TBC)

简介

整体二分是 CDQ 分治的一个变体。即分治维度为答案的 CDQ 分治。

使用前提

同 CDQ 分治。

流程

  • 分治区间 \([L, R)\),答案区间 \([l, r)\)
    1. \([l, mid)\) 的贡献统计到数据结构中
    2. 遍历区间 \([L, R)\) 中的每一个查询
    3. 如果答案在 \([l, mid)\) 范围,那么把它分在左段
    4. 如果答案在 \([mid, r)\) 范围,那么把它分在右段
    5. 分治区间 \([l, mid)\)
    6. 分治区间 \([mid, r)\)

具体实现

咕咕咕