CDQ分治学习笔记(三维偏序题解)
2024-09-01 16:37:03
首先肯定是要膜拜CDQ大佬的。
题目背景
这是一道模板题
可以使用bitset,CDQ分治,K-DTree等方式解决。
题目描述
有 nn 个元素,第 ii 个元素有 a_iai、b_ibi、c_ici 三个属性,设 f(i)f(i) 表示满足 a_j \leq a_iaj≤ai 且 b_j \leq b_ibj≤bi 且 c_j \leq c_icj≤ci 的 jj 的数量。
对于 d \in [0, n)d∈[0,n),求 f(i) = df(i)=d 的数量
输入输出格式
输入格式:
第一行两个整数 nn、kk,分别表示元素数量和最大属性值。
之后 nn 行,每行三个整数 a_iai、b_ibi、c_ici,分别表示三个属性值。
输出格式:
输出 nn 行,第 d + 1d+1 行表示 f(i) = df(i)=d 的 ii 的数量。
输入输出样例
输入样例#1: 复制
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
输出样例#1: 复制
3
1
3
0
1
0
1
0
0
1
怎么看三维偏序呢?
其实就是一个三维的逆序对,没有这么高大上。
回想二维逆序对(普通逆序对)的求解方法:
1、树状数组
利用树状数组的前缀和查询性质,把原数组离散化成相对大小,然后从后往前查询,插入
2、归并排序
归并排序(这和CDQ分治很像,非常像,甚至可以说:归并排序就是cdq分治求二维偏序)
于是,回到正题,三维逆序对,哦不,是三维偏序。
第一维把它排序(在二维逆序对里,第一维是排好序的)
第二维把它塞到归并排序里,去求满足二维的个数,如果满足,塞到树状数组里
第三维用树状数组维护前缀和,就像求二维逆序对那样直接找出来个数。因为经过了前两层的筛选,这一层统计的个数就是最终的答案。
对于CDQ来说,其实最难得部分就是怎么合并两个区间。
说起来非常简单吧。。。但是作为一直规避归并排序的我来说,还是有小小的问题的。。
塞代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
struct node
{
int nth,a,b,c;
}a[maxn];
int n,k;
int f[maxn],same[maxn],t[maxn<<],ans[maxn];
inline int lowbit(int x)//树状数组
{
return x & - x ;
}
void add(int x,int y)
{
for(;x<=k;x+=lowbit(x))
{
t[x]+=y;
}
}
int ask(int x)
{
int res=;
for(;x;x-=lowbit(x))
{
res+=t[x];
}
return res;
}
bool cmp1(node a,node b)//对第一维进行排序
{
if(a.a!=b.a)return a.a<b.a;//第一关键字自然是第一个元素
if(a.b!=b.b)return a.b<b.b;//第二关键字尽量保证(题目要求大于等于)
else return a.c<b.c;
}
bool cmp2(node a,node b)
{
if(a.b!=b.b)return a.b<b.b;//归并时第二维进行排序
if(a.c!=b.c)return a.c<b.c;
else return a.a<b.a;
}
void cdq(int l,int r)
{
if(l==r)
return;
int mid=l+r>>;
cdq(l,mid);
cdq(mid+,r);
sort(a+l,a++r,cmp2);//直接排序,下面计算答案贡献
for(int i=l;i<=r;i++)
{
if(a[i].a<=mid)//如果元素小于mid就说明符合二维的偏序
{
add(a[i].c,);//塞到树状数组里面
}
else
{
ans[a[i].nth]+=ask(a[i].c);//要不然就统计答案
}
}
for(int i=l;i<=r;i++)
{
if(a[i].a<=mid)
add(a[i].c,-);这里还要更新回去,给下一个分治用(注意,不能用memset,太大了,而且上面的if一定要加,可以省去不少个log的复杂度)
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
a[i].nth=i;//第一维
}
sort(a+,a+n+,cmp1);
for(int i=;i<=n;)
{
int j=i+;
while(j<=n&&a[i].a==a[j].a&&a[i].b==a[j].b&&a[i].c==a[j].c)
j++;
while(i<j)
same[a[i++].nth]=a[j-].nth;//去重
}
for(int i=;i<=n;i++)
{
a[i].a=i;
}
cdq(,n);
for(int i=;i<=n;i++)
f[ans[same[a[i].nth]]]++;
for(int i=;i<n;i++)
printf("%d\n",f[i]);
return ;
}
最新文章
- 关于Block的copy和循环引用的问题
- JSONArray遍历
- 278. First Bad Version
- Tkinter教程之Message篇
- HTTP请求和响应详解
- 关于html文档的规范
- session源码剖析
- 华为oj之等差数列前n项和
- 关于MySql经典高频查询语句的整理
- pytorch, LSTM介绍
- 【C#写日志两个简单方法】
- virtualbox中 Ubuntu挂载共享文件夹
- 一个良好划分Activity创建步骤的BaseActivity
- 【python001-IDLE】
- js访3d上下轮播图
- SharePoint 列表多表联合查询
- bzoj 3779: 重组病毒
- 复习静态页面polo-360
- rcnn ->;fast rcnn->;faster rcnn物体检测论文
- Java Socket网络编程Client端详解