三维偏序(陌上花开)---洛谷P3810&&BZOJ3262(cdq分治--归并排序+树状数组)
洛谷题目链接https://www.luogu.org/problem/P3810
BZOJ题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=3262
Description
有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。
现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。
显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
Input
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),表示第i朵花的属性
Output
包含N行,分别表示评级为0...N-1的每级花的数量。
Sample Input
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
Sample Output
3
1
3
0
1
0
1
0
0
1
。。。蜜汁BUG,重构之后才过了QAQ
三维偏序比二维偏序多了一维,但我们还是可以按照二维偏序的思路来想。先固定住第一维,然后对于第二维用归并排序,第三维用树状数组。
我们在归并的时候考虑 [l,mid] 对 [mid+1,r] 的贡献。因为我们已经按属性 a 排过序了,所以在排序属性 b 的时候,无论属性 a 怎么被打乱,[mid+1,r] 所有元素的属性 a 一定不小于 [l,mid] 中所有元素的属性 a,那么我们就可以把[l,mid]内的属性z一个个放到树状数组里面统计了,和二维偏序是一样的做法。接下来还有一个比较重要的就是重复元素--由于这并不是真真的坐标,所以他们会重和,所以我们需要对重复的元素进行剔除和累加。
以下是AC代码:
#include <bits/stdc++.h>
using namespace std;
const int mac=1e5+10;
const int maxn=2e5+10;
int n,m;
int ans[mac],c[maxn];
struct node
{
int x,y,z,ans,f;
}a[mac],b[mac];
bool cmp(node a,node b)
{
if (a.x!=b.x) return a.x<b.x;
if (a.y!=b.y) return a.y<b.y;
return a.z<b.z;
}
int lowbit(int x)
{
return x&-x;
}
void update(int pos,int val)
{
while (pos<=m){
c[pos]+=val;
pos+=lowbit(pos);
}
}
int query(int pos)
{
int sum=0;
while (pos>0){
sum+=c[pos];
pos-=lowbit(pos);
}
return sum;
}
void cdq(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
int ll=l,rr=mid+1,cnt=l-1;
while (ll<=mid && rr<=r){
if (a[ll].y<=a[rr].y){//这个时候后半段对前半段是不会产生贡献的,所以不用统计前半段的答案
update(a[ll].z,a[ll].f);
b[++cnt]=a[ll++];
}
else {
a[rr].ans+=query(a[rr].z);
b[++cnt]=a[rr++];
}
}
while (ll<=mid){
update(a[ll].z,a[ll].f);//实际上这里的这个是没有用的,只不过是为了方便之后的清空
b[++cnt]=a[ll++];
}
while (rr<=r){
a[rr].ans+=query(a[rr].z);
b[++cnt]=a[rr++];
}
for (int i=l; i<=mid; i++) update(a[i].z,-a[i].f);
cnt=0;
for (int i=l; i<=r; i++) a[i]=b[i];
}
int main()
{
scanf ("%d%d",&n,&m);
for (int i=1; i<=n; i++){
scanf ("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
a[i].f=1;
}
sort(a+1,a+1+n,cmp);
int cnt=1;
for (int i=2; i<=n; i++){
if (a[i].x==a[cnt].x && a[i].y==a[cnt].y && a[i].z==a[cnt].z)
a[cnt].f++;//f保留的是重复元素的个数
else a[++cnt]=a[i];
}
cdq(1,cnt);
for (int i=1; i<=cnt; i++){
ans[a[i].ans+a[i].f-1]+=a[i].f;//由于=是成立的,所以我们要加上相等的个数
}
for (int i=0; i<n; i++)
printf ("%d\n",ans[i]);
return 0;
}
上一篇: js 玩转正则表达式之语法高亮
推荐阅读
-
陌上花开 HYSBZ - 3262 三维偏序问题 CDQ分治+树状数组
-
三维偏序(陌上花开)---洛谷P3810&&BZOJ3262(cdq分治--归并排序+树状数组)
-
Luogu P3810 【模板】三维偏序(陌上花开) CDQ分治 树状数组
-
P3810-[模板]三维偏序(陌上花开)【CDQ分治,树状数组】
-
洛谷P3810(陌上花开)(三维偏序,cdq分治)
-
洛谷 - P3810 【模板】三维偏序(陌上花开)(CDQ分治套树状数组)
-
洛谷 P3810 【模板】三维偏序(陌上花开)【cdq 分治】【树状数组】
-
【题解】洛谷P3810【模板】三维偏序(陌上花开)cdq分治+树状数组
-
洛谷P3810 【模板】三维偏序(陌上花开)【CDQ分治、树套树】
-
陌上花开 bzoj3262 CDQ分治套树状数组 三维偏序问题