P3810-[模板]三维偏序(陌上花开)【CDQ分治,树状数组】
程序员文章站
2022-05-14 18:42:09
...
正题
题目链接:https://www.luogu.com.cn/problem/P3810
题目大意
个三元组,
对于每个,求有多少个
解题思路
先按照排序,然后对于这一维进行分治,之后用树状数组计算这一维的结果即可。
要注意的是统计的时候要在结构体里,不然它不会随着排序而交换。
时间复杂度
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
struct node{
int a,b,c,w,ans;
}a[N],b[N];
int n,m,k,ask[N];
struct Tree_Array{
#define lowbit(x) (x&-x)
int t[N];
void Change(int x,int z){
while(x<=k){
t[x]+=z;
x+=lowbit(x);
}
}
int Ask(int x){
int ans=0;
while(x){
ans+=t[x];
x-=lowbit(x);
}
return ans;
}
#undef lowbit(x)
}Ta;
bool Cmp(node x,node y){
if(x.a!=y.a) return x.a<y.a;
return (x.b==y.b)?(x.c<y.c):(x.b<y.b);
}
bool cMp(node x,node y)
{return (x.b==y.b)?(x.c<y.c):(x.b<y.b);}
void Cdq(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
Cdq(l,mid);
Cdq(mid+1,r);
sort(a+l,a+mid+1,cMp);
sort(a+mid+1,a+r+1,cMp);
int k=l;
for(int i=mid+1;i<=r;i++){
while(k<=mid&&a[k].b<=a[i].b)
Ta.Change(a[k].c,a[k].w),k++;
a[i].ans+=Ta.Ask(a[i].c);
}
for(int i=l;i<k;i++)
Ta.Change(a[i].c,-a[i].w);
return;
}
int main()
{
scanf("%d%d",&m,&k);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&b[i].a,&b[i].b,&b[i].c);
sort(b+1,b+1+m,Cmp);
for(int i=1,c=0;i<=m;i++){
c++;
if(b[i].a!=b[i+1].a||b[i].b!=b[i+1].b||b[i].c!=b[i+1].c)
a[++n]=b[i],a[n].w=c,c=0;
}
Cdq(1,n);
for(int i=1;i<=n;i++)
ask[a[i].ans+a[i].w-1]+=a[i].w;
for(int i=0;i<m;i++)
printf("%d\n",ask[i]);
}
上一篇: 我的俄罗斯方块
下一篇: 洛谷P3810 陌上花开(CDQ分治)
推荐阅读
-
陌上花开 HYSBZ - 3262 三维偏序问题 CDQ分治+树状数组
-
BZOJ 3262: 陌上花开 (cdq分治,三维偏序)
-
bzoj 3262 :陌上花开 (cdq分治 三维偏序)
-
【bzoj3262】陌上花开(cdq分治解决三维偏序问题)一些总结
-
BZOJ - 3262 陌上花开 CDQ分治 三维偏序
-
BZOJ 3262 陌上花开 三维偏序,CDQ分治
-
三维偏序(陌上花开)---洛谷P3810&&BZOJ3262(cdq分治--归并排序+树状数组)
-
P3810 -三维偏序(陌上花开)cdq-分治
-
Luogu P3810 【模板】三维偏序(陌上花开) CDQ分治 树状数组
-
CDQ分治--模板 BZOJ 3262--陌上花开【三维偏序】