cdq 分治:
一个长度为 \(n\) 的序列，统计有一些特性的点对 \((i,j)\) 的数量/找到一对点 \((i,j)\) 使得一些函数的值最大。对于这一类问题，我们考虑使用 \(\rm cdq\) 分治思想来解决。
- 什么是 \(\rm cdq\) 分治思想？
\(\rm cdq\) 解决这种问题所使用的是分治思想，但却有些不同，具体流程如下：
-
假设我们现在要求的是 \([l,r]\) 这个区间的所有点对所对应的答案。
-
令中点 \(mid=(l+r)/2\)
-
将点对分为三类：
1.\(x\) 和 \(y\) 均在 \([l,mid]\) 中的 \((x,y)\) 点对
2.\(x\) 在 \([l,mid]\) 中，\(y\) 在 \([mid+1,r]\) 中的 \((x,y)\) 点对
3.\(x\) 和 \(y\) 均在 \([mid+1,r]\) 的 \((x,y)\) 的点对
-
此时对 1、3 类点对进行递归计算，并设法求出第 2 种点对的答案。
Solution:
回到 P3810 【模板】三维偏序 中，在本题中 \(\rm cdq\) 分治思想如何应用？
首先简化一下问题，将点按 \(a\) 排序，此时已经满足了第一个条件。
那么我们考虑在 \(\rm cdq\) 过程中第三种点对如何去求。
此时我们为了方便处理，对左右两半分别按 \(b\) 从小到大进行归并排序。
维护两个指针 \(i\) 和 \(j\) 分别是 \([l,mid]\) 和 \([mid+1,r]\) 归并到哪，同时维护一颗权值树状数组。比较 \(i\) 和 \(j\) 两点 \(b\) 的大小并插入，假如此时我们插入的是 \(i\)。 那么我们更新 \(p[i].c\) 。否则我们可以直接前缀和统计答案。
记得去重。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m;
struct point{
int x,y,z;
int cnt,ans;
}p[N],tmp[N];
struct BIT{
int t[N<<1];
int lowbit(int x){return x&-x;}
void add(int x,int k){
while(x<=m){
t[x]+=k;
x+=lowbit(x);
}
return;
}
int sum(int x){
int ret=0;
while(x>0){
ret+=t[x];
x-=lowbit(x);
}
return ret;
}
}tree;
bool cmp(struct point p1,struct point p2){
if(p1.x!=p2.x)return p1.x<p2.x;
if(p1.y!=p2.y)return p1.y<p2.y;
return p1.z<p2.z;
}
void cdq(int l,int r){
if(l>=r)return;
int mid=(l+r>>1);
cdq(l,mid);cdq(mid+1,r);
int cnt=0;
int i=l,j=mid+1;
while(i<=mid&&j<=r){
if(p[i].y<=p[j].y)tree.add(p[i].z,p[i].cnt),tmp[++cnt]=p[i++];
else{
p[j].ans+=tree.sum(p[j].z);
tmp[++cnt]=p[j++];
}
}
while(i<=mid)tree.add(p[i].z,p[i].cnt),tmp[++cnt]=p[i++];
while(j<=r)p[j].ans+=tree.sum(p[j].z),tmp[++cnt]=p[j++];
for(int i=l;i<=mid;i++)tree.add(p[i].z,-p[i].cnt);
for(int i=l;i<=r;i++)p[i]=tmp[i-l+1];
return;
}
int res[N];
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y>>p[i].z,p[i].cnt=1;
sort(p+1,p+n+1,cmp);
int tmpcnt=1;
for(int i=2;i<=n;i++){
if(p[i].x==p[tmpcnt].x&&p[i].y==p[tmpcnt].y&&p[i].z==p[tmpcnt].z){
p[tmpcnt].cnt++;
continue;
}
p[++tmpcnt]=p[i];
}
cdq(1,tmpcnt);
//for(int i=1;i<=n;i++)cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].z<<" "<<f[i]<<" "<<p[i].cnt<<endl;
for(int i=1;i<=tmpcnt;i++)res[p[i].ans+p[i].cnt-1]+=p[i].cnt;
for(int i=0;i<n;i++)cout<<res[i]<<"\n";
return 0;
}