洛谷P3810 陌上花开
题解：
CDQ分治模板题。
一维排序，二维归并，三维树状数组。
核心思想是分治，即计算左边区间对右边区间的影响。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n, k, m;
struct node{
int x, y, z, id, w;
bool operator < (const node &A)const{
if(A.x == x && A.y == y) return z < A.z;
else if(A.x == x) return y < A.y;
return x < A.x;
}
}a[N], b[N], d[N];
int ans[N], c[N], cnt[N];
vector <int> v1, v2[N] ;
int lowbit(int x) {
return x& (-x);
}
void add(int x, int v) {
for(int i = x; i < N; i += lowbit(i)) c[i] += v;
}
int query(int x) {
int ans = 0;
for(int i = x; i; i -= lowbit(i)) ans += c[i];
return ans;
}
void cdq(int l, int r) {
if(l == r) return ;
int mid = (l + r) >> 1;
cdq(l, mid), cdq(mid + 1, r) ;
int t1 = l, t2 = mid + 1;
for(int i = l; i <= r; i++) {
if((t1 <= mid && a[t1].y <= a[t2].y) || t2 > r) {
add(a[t1].z, a[t1].w);
b[i] = a[t1++];
} else {
cnt[a[t2].id] += query(a[t2].z);
b[i] = a[t2++];
}
}
for(int i = l; i <= mid; i++) add(a[i].z, -a[i].w);
for(int i = l; i <= r; i++) a[i] = b[i];
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y >> a[i].z;
a[i].id = i;
}
sort(a + 1, a + n + 1);
int num = 1;
for(int i = 2; i <= n + 1; i++) {
if(a[i].x != a[i - 1].x || a[i].y != a[i - 1].y || a[i].z != a[i - 1].z) {
d[++m] = a[i - 1];
d[m].w = num;
num = 1;
v2[a[i - 1].id] = v1;
v1.clear();
} else {
num++;
v1.push_back(a[i - 1].id) ;
}
}
for(int i = 1; i <= m; i++) a[i] = d[i];
cdq(1, m);
for(int i = 1; i <= m; i++) {
int sz = v2[a[i].id].size();
for(auto v : v2[a[i].id]) cnt[v] += cnt[a[i].id] + sz;
cnt[a[i].id] += sz;
}
for(int i = 1; i <= n; i++) ans[cnt[i]]++;
for(int i = 0; i < n; i++) cout << ans[i] << '\n';
return 0;
}
/*
3 4
1 2 3
1 2 3
2 1 3
*/