CDQ分治 模板
- CDQ分治 模板 推荐度:
- 相关推荐
CDQ分治 模板
例题
Link.
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long longint n,k,N,ans[2000005];
struct zz{int x,y,z,ans,tot;
}a[100005],b[100005];
bool cmp(zz x,zz y){ return x.x==y.x?(x.y==y.y?x.z<y.z:x.y<y.y):x.x<y.x; } //排序时处理第一维相同,后两位不同的情况。
bool smp(zz x,zz y){ return x.y==y.y?x.z<y.z:x.y<y.y; }int Lowbit(int x){ return x&(-x);}
struct Bit_Tree{ll bit[4000005];int Lowbit(int x){ return x&(-x); }void Insert(int x,ll val){ for(int i=x;i<=k;i+=Lowbit(i)) bit[i]+=val; }ll Find(int x){ ll ans=0; for(int i=x;i;i-=Lowbit(i)) ans+=bit[i]; return ans; }
}T;void CDQ(int l,int r){if(r<=l) return ; int mid=(l+r)>>1;CDQ(l,mid),CDQ(mid+1,r); //分治 sort(a+l,a+mid+1,smp),sort(a+mid+1,a+r+1,smp); //对于上一次的序列排序,这样就不用在中间双指针排序了,因为树状数组,所以也没有加复杂度。 int p=l,q=mid+1; //前半列和后半列的开头。 while(q<=r){while(p<=mid&&a[p].y<=a[q].y) T.Insert(a[p].z,a[p].tot),p++; //答案要求三维都大,而我排序的是三维都小的情况,所以前半列对后半列产生贡献。 a[q].ans+=T.Find(a[q].z);q++;}for(int i=l;i<=p-1;i++) T.Insert(a[i].z,-a[i].tot); //p-1是因为p的这位是不满足条件的,退了while。
}int main(){cin>>N>>k;for(int i=1;i<=N;i++) scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);sort(b+1,b+N+1,cmp);for(int i=1;i<=N;i++){int now=1;while(b[i].x==b[i+1].x&&b[i].y==b[i+1].y&&b[i].z==b[i+1].z) now++,i++; //相同的*在一起。 n++,a[n]=b[i],a[n].tot=now;}CDQ(1,n);for(int i=1;i<=n;i++) ans[a[i].ans+a[i].tot-1]+=a[i].tot;for(int i=0;i<N;i++) printf("%d\n",ans[i]);return 0;
}
最新文章
- 移动互联网应用如何赚钱?
- 虚拟机LINUX系统下安装JKD(附详细操作过程截图)
- 《棒球殿堂》:棒球联盟LEAGUE·埼玉西武狮
- Java程序员学习Rust编程
- Java后端技术框架
- 创建Firebase项目并接入Firebase推送: Firebase Cloud Messaging (FCM)
- 目标检测~总结
- Linux上杀毒软件有哪些?
- JAVA方法SQL语句执行顺序
- 数据库的升序降序排列
- webrtc janus服务器部署在公网,coturn转发媒体流
- Hadoop安装
- 将列表(含字典)数据写入Excel
- Python中call的用法
- PVE安装ros系统
- Java中的byte[]char[]intString数据类型转换
- 锁(Locks)