题解-P3810

P3810 【模板】三维偏序(陌上花开)

更好的阅读体验1

更好的阅读体验2


前置算法

  • 树状数组求逆序对
  • 归并排序求逆序对

解题之前,让我们来看一看弱化版本 ( o) 二维偏序


题意

给定两个长度为数组 (a_1,a_2,dots,a_n),(b_1,b_2,dots,b_n) 求对于每一个 (i),(a_jle a_i) 且 (b_jle b_i) 的 (j) 有多少个。

解法1

考虑用结构体把数组存起来,对 (a) 进行排序,再用一个值域树状数组维护 (b) 值即可。

还没完。由于可能出现 (a_i=a_j) 且 (b_i=b_j) 的情况,所以需要去重。

提到去重,就要在结构体里面多加一个 (x) 。 (x_i) 表示与 (a_j=a_i,b_j=b_i) 的 (j) 的个数,(x_i) 初始为 (1)

去重毒瘤的要死

解法2

还是用结构体存,对 (a) 进行排序+去重,后面考虑用归并排序来求

回想一下归并排序求逆序对,我们求的是 (a_i) 作为逆序对 ((j,i)) 的 (j) 的总个数。

在这里,(a) 已经按大小排好了,所以我们只考虑对 (b) 值求逆序对就行了。

深刻注意解法2


三维偏序

第一步

和二维偏序一样,先按 (a) 值排好序,去重

第二步

为了简化题目,先考虑简易版本不存在 (a_i=a_j) 且 (b_i=b_j) 且 (c_i=c_j) 的情况,标准版本放在第三步。

进入到今天的正题: CDQ 讲解部分。

CDQ 分治,顾名思义,是一种分治。而分治,就需要把 ([l,r]) 分为 ([l,mid]) 和 ([mid+1,r]) 。而对于我们要寻找的一个符合 (a_jle a_i,b_jle b_i,c_jle c_i) 的点对 ((i,j)) 必须符合以下三种情况之一:

  1. (1le i,jle midgets) 这在递归处理左半边时已经处理了
  2. (midlt i,jle ngets) 这在递归处理右半边时已经处理了
  3. (1le i,jle ngets) 这是我们在递归之后需要处理的点对

按分治三部曲走,接下来就是合并左右区间并统计答案了了,这里按归并排序求逆序对的思路来。

由于 (a,b) 值都被我们处理好了,接下来就是毒瘤的 (c) 值,用树状数组维护。

在合并中,我们分两种情况:

  1. 此时的最小值在左,那么我们让树状数组的左边那个数的 (c) 值位置加一
  2. 此时的最小值在右,那么我们让答案加上树状数组从 (1) 到右边数的 (c) 值位置的和

如果搞不懂为什么左是加,右是查,建议重新看一看归并排序求逆序对。

注意:每一次使用完后树状数组要清空。如果单纯 memset,会超时(因为是 (O(n)) ),清空应该对于每一个被存放在树状数组里的 (c_i) ,其在树状数组里面的值 (-1)

int tmp[maxn]; // 临时存放合并好的值的数组
void CDQ(int l,int r){
	if(l == r) return; 
	int mid = l + r >> 1,p = l,q = mid + 1,len = 0;
	CDQ(l,mid),CDQ(mid + 1,r); // 递归处理
	while(p <= mid && q <= r){ // 合并子区间
		if(a[p].b <= a[q].b) bit.update(a[p].c,1),tmp[++len] = a[p++]; // 选左边,此时更新树状数组
		else a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++]; // 选右边,此时答案要加上值域树状数组的查询 
	}
	while(p <= mid) bit.update(a[p].c,1),tmp[++len] = a[p++]; // 归并左边剩下部分
	while(q <= r) a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++]; // 归并右边剩下部分
	for(int i = l;i <= mid;++i) bit.update(a[i].c,-1); // 清空
	for(int i = 1;i <= len;++i) a[l + i - 1] = tmp[i]; // 把临时数组里的值拷贝到原数组
}

第三步

由于第二步只能处理不存在相同的情况,接下来讲解如果存在 (a_i=a_j,b_i=b_j,c_i=c_j) 的 ((i,j)) 该怎么处理。

注意刚才我们树状数组是这样更新的:bit.update(a[p].c,1)

这里的 1 实际上就是 (a_s=a_p,b_s=b_p,c_s=c_p) 的 (s) 的个数,记为 (x) ,(x_i) 我们在去重时求出。

因此代码如下:

int tmp[maxn]; 
void CDQ(int l,int r){
	if(l == r) return;
	int mid = l + r >> 1,p = l,q = mid + 1,len = 0;
	CDQ(l,mid),CDQ(mid + 1,r);
	while(p <= mid && q <= r){
		if(a[p].b <= a[q].b) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
		else a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++]; 
	}
	while(p <= mid) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
	while(q <= r) a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
	for(int i = l;i <= mid;++i) bit.update(a[i].c,-a[i].x);
	for(int i = 1;i <= len;++i) a[l + i - 1] = tmp[i];
}

第四步

这时 CDQ 分治已经完成了,我们现在需要统计答案

按照刚才的代码,a[i].ans 表示 (a_jle a_i,b_jle b_i,c_jle c_i) 但不包括 (a_j=a_i,b_j=b_i,c_j=c_i) 的 (j) 的个数,而 a[i].x 正好表示了 (a_j=a_i,b_j=b_i,c_j=c_i) 的 (j) 的个数。于是 a[i].ans + a[i].x 就是去重后第 (i) 个点的答案。

for(int i = 1;i <= cnt;++i) res[a[i].ans + a[i].x - 1] += a[i].x; // 注意是 + a[i].x,因为还有与 i 值相同所有 j,其总个数是 a[i].x
for(int i = 0;i < n;++i) printf("%d
",res[i]);

(color{#52C41A} exttt{AC CODE})

#include<stdio.h>
#include<algorithm>
const int maxn = 114514;
int n,k;
struct BIT{
	int t[maxn << 1];
	int lowbit(int i){return i & -i;}
	void update(int i,int x){for(;i <= k;i += lowbit(i)) t[i] += x;} 
	int query(int i){int ans = 0;for(;i;i -= lowbit(i)) ans += t[i];return ans;}
} bit; // 树状数组
struct number{
	int a,b,c,ans,x;
	bool operator<(const number& y) const{return a != y.a ? a < y.a : b != y.b ? b < y.b : c < y.c;}
} a[maxn],tmp[maxn]; // 数的结构体
int res[maxn];
void CDQ(int l,int r){
	if(l == r) return;
	int mid = l + r >> 1,p = l,q = mid + 1,len = 0;
	CDQ(l,mid),CDQ(mid + 1,r);
	while(p <= mid && q <= r){
		if(a[p].b <= a[q].b) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
		else a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++]; 
	}
	while(p <= mid) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
	while(q <= r) a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
	for(int i = l;i <= mid;++i) bit.update(a[i].c,-a[i].x);
	for(int i = 1;i <= len;++i) a[l + i - 1] = tmp[i];
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= n;++i) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c),a[i].x = 1,a[i].ans = 0;
	std::sort(a + 1,a + n + 1); // 排序
	int cnt = 1;
	for(int i = 2;i <= n;++i)
		if(a[i].a == a[cnt].a && a[i].b == a[cnt].b && a[i].c == a[cnt].c) ++a[cnt].x; // 如果遇到与 i 一样的,x 值就要自加一
		else a[++cnt] = a[i];
	CDQ(1,cnt); // 注意不是 CDQ(1,n)
	for(int i = 1;i <= cnt;++i) res[a[i].ans + a[i].x - 1] += a[i].x;
	for(int i = 0;i < n;++i) printf("%d
",res[i]);
	return 0;
}
hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » 题解-P3810