陌上花开 CDQ分治
传送门：https://www.luogu.org/problemnew/show/P3810
题意：
[有n 个元素，第 i 个元素有 a_i、 b_i、 c_i 三个属性，设 f(i) 表示满足 a_jleq a_i 且 b_j leq b_i且 c_j leq c_i的 j 的数量。\
对于 d in [0, n]，求 f(i) = d 的数量
]
题解：
CDQ分治模板题，
我们将第一维在主函数排序后，cdq分治里面，每次将左半边和右半边按照y排序，因为一开始的x是已经排序过了的，所以分治将其分为左半边和右半边时，左半边的x还是小于右半边的x，因此维护右半边的位置i和左半边的位置j，如果y[j]<y[i]的话，我们就可以将z[j]丢进树状数组中，直到y[j]>=y[i]时，不满足偏序关系的时候，我们就可以直接树状数组查询小于z[i]的前半部分的j的个数，这样，这么多个数就满足三维的偏序关系。
1.x的偏序关系已经在主函数里面处理，所以分治分了后前一半的x小于后一半的x
2.y的偏序关系是两个指针对着扫了，一遍，将满足y[j]<y[i]的z[j]丢进了树状数组统计个数
3.z的偏序关系是从树状数组中查的小于z[i]的z[j]有多少个
一直这样分治下去，我们就可以得到最终的答案
这个题有一个坑点就是，当x,y,z都相同时，在分治的时候，本来它们相互之间都有贡献，可是cdq的过程中只有左边的能贡献右边的。这可怎么办呢？我们直接离散化后，给定一个权值，这样算贡献就不会算错了
代码：
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********
")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]
"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]
"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]
"
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
struct node {
int x, y, z;
int cnt;
int ans;
} a[maxn];
bool cmpx(node a, node b) {
if(a.x == b.x && a.y == b.y) return a.z < b.z;
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool cmpy(node a, node b) {
if(a.y == b.y && a.z == b.z) return a.x < b.x;
if(a.y == b.y) return a.z < b.z;
return a.y < b.y;
}
int lowbit(int x) {
return x & (-x);
}
int bit[maxn];
void add(int pos, int val) {
while(pos < maxn) {
bit[pos] += val;
pos += lowbit(pos);
}
}
int sum(int pos) {
int res = 0;
while(pos) {
res += bit[pos];
pos -= lowbit(pos);
}
return res;
}
int num[maxn];
void CDQ(int l, int r) {
if(l == r) {
a[l].ans += a[l].cnt - 1;
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(j <= mid && a[j].y <= a[i].y) {
add(a[j].z, a[j].cnt);
j++;
}
a[i].ans += sum(a[i].z);
}
for(int i = l; i < j; i++) {
add(a[i].z, -a[i].cnt);
}
}
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) {
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
a[i].ans = 1;
}
sort(a + 1, a + n + 1, cmpx);
int tot = 0;
for(int i = 1; i <= n; ++i) {
if(i != 1 && a[i].x == a[i - 1].x && a[i].y == a[i - 1].y && a[i].z == a[i - 1].z) a[tot].cnt++;
else a[++tot] = a[i], a[tot].cnt = 1;
}
CDQ(1, tot);
sort(a + 1, a + tot + 1, cmpx);
for(int i = 1; i <= tot; i++) {
num[a[i].ans] += a[i].cnt;
}
for(int i = 1; i <= n; i++) {
printf("%d
", num[i]);
}
return 0;
}