笔记汇总
离线算法 具有 判定困难、全局判定 的特点。
分治,是一种将大的问题拆分成小问题解决的算法。
在修改、询问相互独立的前提下,我们可以用分治统计满足序数关系点对的数量。
这是一道二维偏序的模板题,由于是序数关系,且不用强制在线,让其中一个条件有序是有必要的,
所以我们可以靠排序降一维(避免高级数据结构),并用归并内的双指针解决。
但是,如果我们是按双关键字排序呢?
回归本题,为什么分治可以统计点对的数量?
因为序列可以划分成很多部分,大的是小部分的组合,
而那些一个在左区间,一个在右区间的点对,
我们已经确定左边所有点和右边所有点的第一维都满足偏序要求的大小关系(因为已经排过序了)。
所以可以将左右区间分别按第二维统计,
然后对于右区间中每个点,统计左区间中符合偏序关系的点的个数
这可以用双指针算法解决。
CDQ分治大致就是这两个基本形式:多维偏序降维 和 动态修改转换成静态修改统一查询。
只要问题能转化成这两个形式,那就可以考虑用CDQ分治了。
实现
一维偏序
排序可判序数关系
二维偏序
双关键字排序降维,归并排序加双指针统计第二关键字可造成贡献。
注意第一关键字顺序不完全决定第二关键字顺序。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n;
int a[N], tmp[N];
long long ans;
void merge(int l, int r)
{
if (l >= r) return;
int m = l + r >> 1;
merge(l, m), merge(m+1, r);
int i = l, j = m+1, k = 0;
while (i <= m && j <= r) {
if (a[i] <= a[j]) tmp[k ++ ] = a[i ++ ];
else tmp[k ++ ] = a[j ++ ], ans += m - (i-1); // [i~m]
}
while (i <= m) tmp[k ++ ] = a[i ++ ];
while (j <= r) tmp[k ++ ] = a[j ++ ];
for (int i = l, j = 0; i <= r; i ++, j ++ ) a[i] = tmp[j];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
merge(1, n);
printf("%lld", ans);
return 0;
}
三维偏序
题目描述
有 $ 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 $ 的数量。
分析
我们先在外部按第一维排好序。
在函数体内,递归地解决左区间和右区间的子问题,然后对于一个在左区间,一个在右区间的点对,我们分别将左右区间按第二维排序,再用双指针+树状数组的方法解决问题。
具体地,对于右区间的每个点,我们遍历左区间,把第二维符合要求的点的第三维塞入树状数组,然后查询第三维也符合要求的点的数目。
在统计贡献时对左区间建树,以统计左区间对右区间造成的贡献(区间内是已统计过的)
如果偏序关系带等号,对于完全相等的元素,需要捆绑起来一起处理(包括二维偏序也要注意这个问题),不然可能会把相等的元素划到左右两个区间去,从而把相等元素的相互贡献漏掉一部分。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 200010;
int n, m;
struct Data
{
int a, b, c, s, res; // s 是单点的贡献(即所有重复数据)
bool operator< (const Data& t) const
{
if (a != t.a) return a < t.a;
if (b != t.b) return b < t.b;
return c < t.c;
}
bool operator== (const Data& t) const
{
return a == t.a && b == t.b && c == t.c;
}
}q[N], w[N];
int tr[M], ans[N]; // 可以用权值线段树替换
int lowbit(int x)
{
return x & -x;
}
void add(int x, int v)
{
for (int i = x; i < M; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
// 归并排序
void merge_sort(int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);
// 双指针统计区间合并时的贡献
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) // 边界
if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
// q[i].b > q[j].b,仅当 q[i].a < q[j].a,则统计此时q[i].b<q[j].b贡献
while (i <= mid) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ];
// i 余下的仍然要加入树,以便于后面清空树状数组
while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ];
// 统计贡献,此时都是满足的
for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].s); // 清空树状数组
for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
q[i] = {a, b, c, 1};
}
sort(q, q + n);
int k = 1;
for (int i = 1; i < n; i ++ )
if (q[i] == q[k - 1]) q[k - 1].s ++ ;
else q[k ++ ] = q[i];
merge_sort(0, k - 1);
for (int i = 0; i < k; i ++ )
ans[q[i].res + q[i].s - 1] += q[i].s;
for (int i = 0; i < n; i ++ ) printf("%d\n", ans[i]);
return 0;
}
$$\huge\color{lightblue}{qpzc}$$