题目链接
曼波~
\(\Large \texttt{注意到直接对第一维排序可以去掉一维。}\)
\(\Large \texttt{注意到使用归并排序可以去掉第二维。}\)
\(\Large \texttt{注意到在归并排序的过程中对以第二维为横坐标，第三维为纵坐标二维数点就可以得到答案。}\)
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct node{int x, y, z, ans, cnt;
}a[N], b[N], tp[N];
int n, k, s[N], out[N], tot;
bool cmp(node a, node b){if(a.x == b.x && a.y == b.y) return a.z < b.z;return a.x == b.x ? a.y < b.y : a.x < b.x;
}
void modify(int x, int k){for(; x < N; x += x & -x){s[x] += k;}
}
int query(int x){int ans = 0;for(; x; x -= x & -x) ans += s[x];return ans;
}
void merge(int l, int r){int mid = (l + r) >> 1;if(l == r) return;merge(l, mid);merge(mid + 1, r);vector<node> v;for(int i = l; i <= mid; i++){v.push_back(a[i]);modify(a[i].z, a[i].cnt);}for(int i = r; i >= mid + 1; i--){while(!v.empty() && v.back().y > a[i].y){modify(v.back().z, -v.back().cnt);v.pop_back();}a[i].ans += query(a[i].z);}while(!v.empty()) modify(v.back().z, -v.back().cnt), v.pop_back();int i = l, j = mid + 1, cnt = l;while(i <= mid && j <= r){if(a[i].y <= a[j].y) tp[cnt++] = a[i++];else tp[cnt++] = a[j++];}while(i <= mid) tp[cnt++] = a[i++];while(j <= r) tp[cnt++] = a[j++];for(int i = l; i <= r; i++) a[i] = tp[i];
}
int main(){cin >> n >> k;for(int i = 1; i <= n; i++){cin >> b[i].x >> b[i].y >> b[i].z;}sort(b + 1, b + n + 1, cmp);for(int i = 1, last = 0; i <= n; i++){if(b[i].x == b[i + 1].x && b[i].y == b[i + 1].y && b[i].z == b[i + 1].z) continue;b[i].cnt = i - last;last = i;a[++tot] = b[i];}merge(1, tot);for(int i = 1; i <= tot; i++){out[a[i].ans + a[i].cnt - 1] += a[i].cnt;}for(int i = 0; i < n; i++){cout << out[i] << '\n';}return 0;
}