P3810 陌上花开(CDQ分治)
程序员文章站
2022-05-14 18:49:50
...
题意:
有个元素,第个元素有,,三个属性,设表示满足且且且的的数量,对于,求的数量
题解:
其实三维偏序就是在二维偏序上加一维而已。
我们先按每个元素的a排序,然后第二维用归并排序,第三维用树状数组。
我们在归并的时候考虑[l,mid]对[mid+1,r]的贡献,因为我们已经按a排序过了,所以在对b排序的时候,无论a怎么被打乱,[mid+1,r]的所有元素的a一定大于等于[l,mid]中所有元素的a,所以第二维是成立的。
在满足前两维都是有序时,第三位就能用树状数组去统计答案了
注意题目中是有取等号的,所以我们要先将元素进行去重后,统计最终的答案
AC代码:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
typedef long long LL;
const int MAXN = 1e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
struct node{ int x,y,z,cnt,res; }a[MAXN],b[MAXN];
int n,m,bit[MAXN<<1],ans[MAXN],cnt;
inline bool cmp(node x,node y){
if(x.x!=y.x) return x.x<y.x;
if(x.y!=y.y) return x.y<y.y;
return x.z<y.z;
}
namespace BIT{
inline int lowbit(int x){ return x&-x; }
inline void add(int x,int val){ for(int i=x;i<=m;i+=lowbit(i)) bit[i]+=val; }
inline int query(int x,int res=0){ for(int i=x;i;i-=lowbit(i)) res+=bit[i]; return res; }
}
using namespace BIT;
inline void CDQ(int l,int r){
if(l==r) return; int mid=(l+r)>>1;
CDQ(l,mid); CDQ(mid+1,r);
int p=l,q=mid+1,tot=l;
while(p<=mid && q<=r){
if(a[p].y<=a[q].y) add(a[p].z,a[p].cnt),b[tot++]=a[p++];
else a[q].res+=query(a[q].z),b[tot++]=a[q++];
}
while(p<=mid) add(a[p].z,a[p].cnt),b[tot++]=a[p++];
while(q<=r) a[q].res+=query(a[q].z),b[tot++]=a[q++];
for(int i=l;i<=mid;i++) add(a[i].z,-a[i].cnt);
for(int i=l;i<=r;i++) a[i]=b[i];
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGE
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].cnt=1;
sort(a+1,a+n+1,cmp); 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].cnt++;
else a[++cnt]=a[i];
}
CDQ(1,cnt);
for(int i=1;i<=cnt;i++) ans[a[i].res+a[i].cnt-1]+=a[i].cnt;
for(int i=0;i<n;i++) printf("%d\n",ans[i]);
return 0;
}