三维偏序
#include<bits/stdc++.h>
using namespace std;
const int maxn=
100004;
int n,m,k,c[maxn<<
1],num[maxn];
struct node{
int x,y,z,w,ans;
}a[maxn],b[maxn];
inline bool cmpx(node p,node q){
if(p.x==
q.x){
if(p.y==q.y)
return p.z<
q.z;
return p.y<
q.y;
}
return p.x<
q.x;
}
inline bool cmpy(node p,node q){
if(p.y==q.y)
return p.z<
q.z;
return p.y<
q.y;
}
inline int lowbit(
int x) {
return x&-
x;}
inline void add(
int x,
int y){
while(x<=
k){
c[x]+=
y;
x+=
lowbit(x);
}
}
inline int ask(
int x){
int sum=
0;
while(x){
sum+=
c[x];
x-=
lowbit(x);
}
return sum;
}
inline 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,cmpy);
sort(a+mid+
1,a+r+
1,cmpy);
int j=
l;
for(
int i=mid+
1;i<=r;i++
){
while(a[j].y<=a[i].y&&j<=mid) add(a[j].z,a[j].w),j++
;
a[i].ans+=
ask(a[i].z);
}
for(
int i=l;i<j;i++
){
add(a[i].z,-
a[i].w);
}
}
int main(){
scanf("%d%d",&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,cmpx);
int d=
0;
for(
int i=
1;i<=n;i++
){
d++
;
if(b[i].x!=b[i+
1].x||b[i].y!=b[i+
1].y||b[i].z!=b[i+
1].z){
a[++m]=b[i],a[m].w=d,d=
0;
}
}
cdq(1,m);
for(
int i=
1;i<=m;i++
){
num[a[i].ans+a[i].w-
1]+=
a[i].w;
//cout<<a[i].ans<<' '<<a[i].w<<endl;
}
for(
int i=
0;i<n;i++
){
printf("%d\n",num[i]);
}
return 0;
}
转载于:https://www.cnblogs.com/wifimonster/p/10270975.html
相关资源：数据结构—成绩单生成器
