首页 > 其他分享 >CDQ分治

CDQ分治

时间：2023-04-26 11:45:24浏览次数：42  
标签：sort return int 分治 mid kmax CDQ include

其本质是对分治的进一步理解
先来看一个问题

二维偏序

给定 \(n\) 个二元组，第 \(i\) 个二元组 \(p_i = (x_i, y_i)\)， 求顺序对个数。
即求满足 \(x_i < x_j\) 且 \(y_i < y_j\) 的 \((i, j)\) 对数

很容易想到以 \(x\) 为第一关键字从小到大排序，\(y\) 用树状数组维护计数即可。

现在我们将该问题升高难度

三维偏序

有 \(n\) 个元素，第 \(i\) 个元素有 \(a_i,b_i,c_i\) 三个属性，设 \(f(i)\) 表示满足 \(a_j \leq a_i\) 且 \(b_j \leq b_i\) 且 \(c_j \leq c_i\) 且 \(j \ne i\) 的 \(j\) 的数量。

对于 \(d \in [0, n)\)，求 \(f(i) = d\) 的数量。

我们发现使用排序和树状数组处理前两位后，最后一位无法处理。

这是我们要用到 CDQ分治。

CDQ分治

假设当前我们在处理 \([l,r]\) 这个区间里的结果，并且我们已经处理完其两个子区间 \([l, mid]\) 和 \([mid + 1, r]\) 的结果。

也就是说，我们现在需要在两个子区间中各选一个元素，并计算结果。

由于我们在分治前将原序列以 \(a\) 为第一关键字从小到大排序，所以 \([l, mid]\) 中所有元素的 \(a\) 均不大于 \([mid + 1, r]\) 中元素的 \(a\)。

我们再将两个子区间按照 \(b\) 值排序，然后使用双指针 + 树状数组 处理最后两维。

大致长这样：

  // 排序
  sort(v + l, v + mid + 1, [](V p, V q) { return p.y < q.y || p.y == q.y && p.z < q.z; });
  sort(v + mid + 1, v + r + 1, [](V p, V q) { return p.y < q.y || p.y == q.y && p.z < q.z; });
  // 双指针
  int j = l;  
  for (int i = mid + 1; i <= r; i++) {
    for (; j <= mid && v[j].y <= v[i].y; j++) {
      Modify(v[j].z, 1); // 树状数组修改
    }
    v[i].res += Query(v[i].z);  // 累加答案
  }

但是当前区间所进行的修改会对其父亲区间产生后效，所以我们需要将它撤回（或者清空）。

  for (j--; j >= l; j--) {
    Modify(v[j].z, -1);
  }

还有一点，由于处理当前区间前先处理两个子区间后在进行了排序，所以子区间的排序不会对当前区间产生影响。

整个代码长这样：

void Cdq(int l, int r) {
  if (l == r) return; // 边界，只有一个元素，不会产生答案，直接返回
  int mid = (l + r) >> 1;
  // 先处理好子区间
  Cdq(l, mid);
  Cdq(mid + 1, r);
  sort(v + l, v + mid + 1, [](V p, V q) { return p.y < q.y || p.y == q.y && p.z < q.z; });
  sort(v + mid + 1, v + r + 1, [](V p, V q) { return p.y < q.y || p.y == q.y && p.z < q.z; });
  int j = l;
  for (int i = mid + 1; i <= r; i++) {
    for (; j <= mid && v[j].y <= v[i].y; j++) {
      Modify(v[j].z, v[j].s);
    }
    v[i].res += Query(v[i].z);
  }
  // 撤回当前区间进行的操作
  for (j--; j >= l; j--) {
    Modify(v[j].z, -v[j].s);
  }
}

纵观整个过程，我们处理的是 \(a_j < a_i\) 且 \(b_j < b_i\) 且 \(c_j < c_i\)，而原题可以取等。所以我们需要将原来的元素集合去重。

至于为什么不直接在分治里取等，原因大致是分类情况太多了。（猜的）

完整代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int kmax = 2e5 + 3;

// 元素，包含三维，数量，结果
struct V {
  int x, y, z, s;
  int res;
} v[kmax];

int n, m, k;
int c[kmax];
long long res[kmax];

int Lowbit(int x) {
  return x & -x;
}

void Modify(int x, int v) {
  for (; x < kmax; x += Lowbit(x)) {
    c[x] += v;
  }
}

int Query(int x) {
  int tot = 0;
  for (; x; x -= Lowbit(x)) {
    tot += c[x];
  }
  return tot;
}

void Cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  Cdq(l, mid);
  Cdq(mid + 1, r);
  sort(v + l, v + mid + 1, [](V p, V q) { return p.y < q.y || p.y == q.y && p.z < q.z; });
  sort(v + mid + 1, v + r + 1, [](V p, V q) { return p.y < q.y || p.y == q.y && p.z < q.z; });
  int j = l;
  for (int i = mid + 1; i <= r; i++) {
    for (; j <= mid && v[j].y <= v[i].y; j++) {
      Modify(v[j].z, v[j].s); // 注意现在修改的值是该元素的数量，不一定是1
    }
    v[i].res += Query(v[i].z);
  }
  for (j--; j >= l; j--) {
    Modify(v[j].z, -v[j].s);
  }
}

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].z);
  }
  // 以x为第一关键字排序
  sort(v + 1, v + n + 1, [](V p, V q) { return p.x < q.x || p.x == q.x && p.y < q.y || p.x == q.x && p.y == q.y && p.z < q.z; });
  // 元素去重
  for (int i = 1; i <= n; i++) {
    if (v[i].x != v[m].x || v[i].y != v[m].y || v[i].z != v[m].z) {
      v[++m] = {v[i].x, v[i].y, v[i].z, 1};
    } else {
      v[m].s++;
    }
  }
  // 分治
  Cdq(1, m);
  // 统计最终答案
  for (int i = 1; i <= m; i++) {
    int num = v[i].res + v[i].s - 1;
    res[num] += v[i].s;
  }
  for (int i = 0; i < n; i++) {
    printf("%lld\n", res[i]);
  }
  return 0;
}

接下来我们看几道练习题

Mokia

我们尝试将一次询问的区间拆分成四个小询问。即对于一组询问 \((x_1, y_1, x_2, y_2)\) 拆分成 \((0, 0)\Rightarrow(x_2,y_2)\)、\((0, 0)\Rightarrow(x_1-1,y_1-1)\)、\((0, 0)\Rightarrow(x_1-1,y_2)\)、\((0, 0)\Rightarrow(x_2,y_1-1)\)，前者对答案做出 \(1\) 的贡献，后者做出 \(-1\) 贡献。

我们发现每组小询问的起始点都是 \((0, 0)\)，所以我们只需记录其终点的位置 \((x, y)\)，这是二维的。

然后由于加入了修改，我们还要考虑时间这一维，总共就是三维。

不需要去重，直接套用分治即可。

注意 \(x - 1\)，\(y - 1\) 可能为 \(0\)，树状数组会卡死。所以需要将所有元素的 \(x\)、\(y\) 各偏移 \(1\)。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int kmax = 2e6 + 3;

struct V {
  int t, x, y;
  int op, res;
} p[kmax];

int n, pc;
int c[kmax];

int Lowbit(int x) { return x & -x; }

void Modify(int x, int v) {
  for (; x <= n; x += Lowbit(x)) {
    c[x] += v;
  }
}

int Query(int x) {
  int tot = 0;
  for (; x; x -= Lowbit(x)) {
    tot += c[x];
  }
  return tot;
}

void Cdq(int l, int r) {
  if (l == r)
    return;
  int mid = (l + r) >> 1;
  Cdq(l, mid), Cdq(mid + 1, r);
  sort(p + l, p + mid + 1, [](V p, V q) { return p.x < q.x || p.x == q.x && p.y < q.y; });
  sort(p + mid + 1, p + r + 1, [](V p, V q) { return p.x < q.x || p.x == q.x && p.y < q.y; });
  int j = l;
  for (int i = mid + 1; i <= r; i++) {
    for (; j <= mid && p[j].x <= p[i].x; j++) {
      if (!p[j].op) {
        Modify(p[j].y, p[j].res);
      }
    }
    if (p[i].op) {
      p[i].res += Query(p[i].y);
    }
  }
  for (j--; j >= l; j--) {
    if (!p[j].op) {
      Modify(p[j].y, -p[j].res);
    }
  }
}

int main() {
  scanf("%d%d", &n, &n);
  n++;
  for (int op, x, y, _x, _y, v; scanf("%d", &op);) {
    if (op == 3)
      break;
    if (op == 1) {
      scanf("%d%d%d", &x, &y, &v);
      p[++pc] = {pc, ++x, ++y, 0, v};
    } else {
      scanf("%d%d%d%d", &x, &y, &_x, &_y);
      // 拆分成四个元素
      p[++pc] = {pc, x, y, 1}, p[++pc] = {pc, ++_x, ++_y, 1};
      p[++pc] = {pc, _x, y, 1}, p[++pc] = {pc, x, _y, 1};
    }
  }
  Cdq(1, pc);
  // 以时间排序
  sort(p + 1, p + pc + 1, [](V p, V q) { return p.t < q.t; });
  for (int i = 1; i <= pc; i++) {
    if (!p[i].op)
      continue;
    printf("%d\n", p[i].res + p[++i].res - p[++i].res - p[++i].res);
    // 四个元素的答案统一到一起
  }
  return 0;
}

CQOI2011 动态逆序对

我们发现=只要求出初始逆序对，然后每次计算出减少的逆序对数量即可。

对于每一个被删的元素， 其减少的逆序对数量由两部分组成。

  1. 位于该元素前面，删除时间比该元素晚，权值比该元素大的元素数量。

  2. 位于该元素后面，删除时间比该元素晚，权值比该元素小的元素数量。

由此不难得出一个元素三个维度的属性，分别是位置、删除时间、权值。

使用CDQ分治即可。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int kmax = 1e5 + 3;

struct Node {
    int e, v, d;
    int o, t;
} c[kmax << 1];

int n, m, ct;
int p[kmax], a[kmax], t[kmax];
long long ans[kmax];

int Lowbit(int x) { return x & (-x); }

void Update(int x, int k) {
    for (; x <= n; x += Lowbit(x)) {
        t[x] += k;
    }
}

int Query(int x) {
    int tot = 0;
    for (; x; x -= Lowbit(x)) {
        tot += t[x];
    }
    return tot;
}

void Cdq(int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    int j = l;
    Cdq(l, mid);
    Cdq(mid + 1, r);
    sort(c + l, c + mid + 1, [](Node p, Node q) { return p.d < q.d; });
    sort(c + mid + 1, c + r + 1, [](Node p, Node q) { return p.d < q.d; });
    for (int i = mid + 1; i <= r; i++) {
        for (; j <= mid && c[j].d <= c[i].d; j++) {
            Update(c[j].v, c[j].e);
        }
        ans[c[i].o] += c[i].e * (Query(n) - Query(c[i].v));
    }
    for (int i = l; i < j; i++) {
        Update(c[i].v, -c[i].e);
    }
    j = mid;
    for (int i = r; i > mid; i--) {
        for (; j >= l && c[j].d >= c[i].d; j--) {
            Update(c[j].v, c[j].e);
        }
        ans[c[i].o] += c[i].e * Query(c[i].v - 1);
    }
    for (int i = mid; i > j; i--) {
        Update(c[i].v, -c[i].e);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[a[i]] = i;
        ct++;
        c[ct] = { 1, a[i], i, 0, ct };
    }
    for (int i = 1, x; i <= m; i++) {
        cin >> x;
        ct++;
        c[ct] = { -1, x, p[x], i, ct };
    }
    Cdq(1, ct);
    for (int i = 0; i < m; i++) {
        if (i)
            ans[i] += ans[i - 1];
        cout << ans[i] << '\n';
    }
    return 0;
}

LIS2

先看看普通的 \(LIS\)。

对于当前考虑的位置 \(i\), 我们需要找到一个 \(j < i\) 且 \(a_j < a_i\) 的 \(f_j\) 的最大值。

我们尝试用树状数组维护。（我们不会删除元素，故最大值不会减少）

复杂度 \(O(n \log n)。\)

但此题是二维的，我们可以尝试分治。

与普通的分治不同的是，我们这里要先处理左子区间，再处理当前区间，最后处理右子区间。因为 dp 数组不能记录当前的答案从哪一位置转移得到，我们只知道这个答案以当前元素结尾。

反之，如果处理完右子区间后在合并处理当前区间，右子区间的答案会算重。

实现细节：

  1. 离散化。
  2. 树状数组撤回操作改清空。
  3. 左 \(\rightarrow\) 当前 \(\rightarrow\) 右的顺序。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int kmax = 1e5 + 3;

struct V {
    int x, y, id;
} p[kmax];

int n, f[kmax];
int b[kmax], m;
int c[kmax];
int res;

int Lowbit(int x) { return x & -x; }

void Modify(int x, int v) {
    for (; x <= m; x += Lowbit(x)) {
        c[x] = max(c[x], v);
    }
}

void Clear(int x) {
    for (; x <= m; x += Lowbit(x)) {
        c[x] = 0;
    }
}

int Query(int x) {
    int tot = 0;
    for (; x; x -= Lowbit(x)) {
        tot = max(tot, c[x]);
    }
    return tot;
}

void Cdq(int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    Cdq(l, mid);
    sort(p + l, p + mid + 1, [](V p, V q) { return p.x < q.x; });
    sort(p + mid + 1, p + r + 1, [](V p, V q) { return p.x < q.x; });
    int j = l;
    for (int i = mid + 1; i <= r; i++) {
        for (; j <= mid && p[j].x < p[i].x; j++) {
            Modify(p[j].y, f[p[j].id]);
        }
        f[p[i].id] = max(f[p[i].id], Query(p[i].y - 1) + 1);
    }
    for (j--; j >= l; j--) {
        Clear(p[j].y);
    }
    sort(p + mid + 1, p + r + 1, [](V p, V q) { return p.id < q.id; });
    Cdq(mid + 1, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
        p[i].id = i;
    }
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        b[i] = p[i].y;
    }
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++) {
        p[i].y = lower_bound(b + 1, b + m + 1, p[i].y) - b;
    }
    Cdq(1, n);
    for (int i = 1; i <= n; i++) {
        res = max(res, f[i]);
    }
    printf("%d\n", res);
    return 0;
}

完结撒花 \ / \ / \ /

标签：sort,return,int,分治,mid,kmax,CDQ,include
From： https://www.cnblogs.com/ereoth/p/17355170.html

相关文章

  • 棋盘覆盖问题——分治法
    问题描述有一个 x （k>0）的棋盘，恰好有一个方格与其他方格不同，称之为特殊方格。现在要用如下图所示的L形骨牌覆盖除了特殊方格以外的其他全部方格，骨牌可以任意旋转，并且任何两个骨牌不能重复。请给出一种覆盖方式。 样例：输入：输出： 思路——分治法：将一个规模为n的问题分解......
  • 分治算法：剑指 Offer 25. 合并两个排序的链表
    题目描述：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 限制：0<=链表长度<=1000 解题思路：    classSolution{publicListNodemergeTwoLists(ListNodel1,ListNodel2){ListNodedum=newListNode......
  • CF1816F Xor Counting - dp - 分治 -
    题目链接：https://codeforces.com/contest/1816/problem/F题解：一道有趣的题。首先发现\(m=1\)和\(m\geq3\)时结论是平凡的。\(m=1\)时结论显然，下面讨论一下\(m\geq3\)时：首先可以构造\([x,(n-x)/2,(n-x)/2,\cdots]\)，其中\(x\)和\(n\)同奇偶，显然此时异或值可以......
  • Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心
    场景1、分治算法的基本思想是将一个计算复杂的问题分成规模较小、计算简单的小问题求解，然后综合各个小问题，得到最终答案。2、穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。3、迭代法(IterativeMethod)无法使用公式一次求解，而需要使用重复结构(即循环)重复执......
  • 【DP】【分治】LeetCode 53. 最大子数组和
    题目链接[https://leetcode.cn/problems/maximum-subarray/description/](53.最大子数组和"https://leetcode.cn/problems/maximum-subarray/description/")思路分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律在数......
  • HDU 4812 D Tree （树上点分治）
    题目地址：HDU4812这题是13年南京区域赛的现场题。树分治思想。树分治的过程中记录下每个子树的所有到达根的路径的积，用best记录下每个积的最小端点，然后再枚举当前子树的每个积，然后用逆元的方法求出当积为k时所需要的另一个端点值，并更新答案。代码如下：#include<iostream>#......
  • POJ 1987 Distance Statistics (树上点分治)
    题目地址：POJ1987点分治模板题，跟POJ1741几乎一样，。。代码如下：#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include<std......
  • SPOJ 1825 FTOUR2 - Free tour II (树上点分治)
    题目地址：SPOJ1825树分治的题果然除了模板题就是金牌题啊。。。这题是一道论文题，想了好长时间。。。。终于过了，，，，注意一个坑点，如果权值全部为负的话，是可以不选任意一条边的，这样权值为0。。。也就是说初始值要设为0。。。具体看漆子超的论文《分治算法在树的路径问题中的应用》......
  • HDU 5016 Mart Master II (树上点分治)
    题目地址：HDU5016先两遍DFS预处理出每个点距最近的基站的距离与基站的编号。然后找重心，求出每个点距重心的距离，然后根据dis[x]+dis[y]<d[y]，用二分找出当前子树中不会被占领的数量，总点数减去即是被占领的数量。这样就可以求出每个点最多占领的点的数量。然后找最大值即可。......
  • Java实现：分治法求最近点对
    /*问题1：如何解决cannotbecasttojava.lang.Comparable问题？产生原因：TreeSet的特点是可排序、不重复，即TreeSet要求存放的对象必须是可排序的。如果对象之间不可排序，就会抛出这个异常。解决：实现Comparable接口问题2：JavaArrayListtoArray()方法解决：https://www.runoo......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99