题意：给出三维空间中的N个点，坐标为不超过K的正整数。对于0≤i<n，求有多少个点满足恰有i个其他点每一维均不大于它。（1≤N≤10^5，1&l3;K≤2*10^5） N维数点问题可以用bitset解决，方法是以第k维（k=1,2,...,N）为关键字排序，每个点维护前k维满足条件的集合，求交。
今天上午WC讲课学到了这个算法，想实践一番。以前听说过一道类似的题，也就是本题。然而这个数据范围不支持啊。
查了查题解：排序搞掉一维，CDQ分治搞掉一维，树状数组搞掉一维；也可以排序+树套树。
糟糕，既不会CDQ分治也不会树套树......
没关系，听说CDQ分治和归并排序求逆序对很像，基本思想是分割序列，两边递归求解，本层只考虑一边对另一边的贡献。
于是，脑补出这样的算法： 1. 以第一维为关键字排序。 2. 在根据第一维排好序的数组上以第二维为关键字归并排序。 3. 归并排序合并时，将左边的点插入按照第三维的权值建立的树状数组，右边的点查询前缀和，第二维相等时优先走左边的点。
结果答案不对。发现自己只计算了左边对右边的贡献，没有计算右边对左边的贡献，而本题的大小比较是带等号的。
我的解决方法是在递归前单独计算这部分代价。
TLE......
每次都直接清空整个树状数组，大概是这个原因。于是离散化了一下，AC了，可是跑得好慢，2000ms+......时间复杂度
看了hzwer的代码，三个方面： 1. 用不着归并排序，对两个子序列直接sort就好。 2. 用不着离散化，把加到树状数组上的值减回去就可以避免清零操作。 3. 用不着单独计算右边对左边的贡献。先合并相同的点，第一步排序时，以第二、三维作为第二、三关键字，这样就保证对一个点的答案有贡献的点都在它左边。
还是把我又长又慢的代码贴上来 QAQ
#include <cstdio>
#include <cctype>
#include <algorithm>
typedef unsigned long long ull;
const int MAX_N = 1e5, MAX_K = 2e5;
using namespace std;
template<typename T>
inline void read(T& x)
{
char c;
while (c = getchar(), !isdigit(c)) ;
x = c - '0';
while (c = getchar(), isdigit(c))
x = x*10 + c - '0';
}
namespace BIT {
int x[MAX_N+1];
inline int lowbit(int x)
{
return x & -x;
}
inline void clean(int n)
{
fill_n(x+1, n, 0);
}
inline void add(int n, int p)
{
while (p <= n) {
++x[p];
p += lowbit(p);
}
}
inline int query(int n, int p)
{
int r = 0;
while (p) {
r += x[p];
p -= lowbit(p);
}
return r;
}
}
int A[MAX_N+1], b[MAX_N+1], t[MAX_N+1], L[MAX_N+1], R[MAX_N+1], cnt[MAX_N+1], ans[MAX_N+1];
struct Data {
int v[3];
} D[MAX_N+1];
inline bool cmp1(int i, int j)
{
int x = D[A[i]].v[1], y = D[A[j]].v[1];
return x < y || x == y && i > j;
}
inline int idx(int k, int x)
{
return lower_bound(b, b+k, x) - b + 1;
}
void merge_sort(int l, int r)
{
if (l == r)
return;
int m = (l+r)/2, p = m, q = m+1, u = D[A[p]].v[0], len = r-l+1, k;
if (u == D[A[q]].v[0]) {
while (q < r && D[A[q+1]].v[0] == u)
++q;
while (p > l && D[A[p-1]].v[0] == u)
--p;
int d = q-p+1;
for (int i = 0; i < d; ++i) t[i] = p+i;
sort(t, t+d, cmp1);
for (int i = 0; i < d; ++i) b[i] = D[A[p+i]].v[2];
sort(b, b+d);
k = unique(b, b+d) - b;
BIT::clean(k);
for (int i = 0; i < d; ++i) {
int j = A[t[i]];
if (t[i] <= m)
cnt[j] += BIT::query(k, idx(k, D[j].v[2]));
else
BIT::add(k, idx(k, D[j].v[2]));
}
}
merge_sort(l, m);
merge_sort(m+1, r);
copy(A+l, A+m+1, L);
copy(A+m+1, A+r+1, R);
for (int i = 0; i < len; ++i) b[i] = D[A[l+i]].v[2];
sort(b, b+len);
k = unique(b, b+len) - b;
BIT::clean(k);
p = q = 0;
for (int i = l; i <= r; ++i) {
if (q == r-m || p < m+1-l && D[L[p]].v[1] <= D[R[q]].v[1]) {
A[i] = L[p++];
BIT::add(k, idx(k, D[A[i]].v[2]));
} else {
A[i] = R[q++];
cnt[A[i]] += BIT::query(k, idx(k, D[A[i]].v[2]));
}
}
}
inline bool cmp(int i, int j)
{
return D[i].v[0] < D[j].v[0];
}
int main()
{
int n, k;
read(n);
read(k);
for (int i = 1; i <= n; ++i) {
A[i] = i;
for (int j = 0; j < 3; ++j)
read(D[i].v[j]);
}
sort(A+1, A+n+1, cmp);
merge_sort(1, n);
for (int i = 1; i <= n; ++i)
++ans[cnt[i]];
for (int i = 0; i < n; ++i)
printf("%d\n", ans[i]);
return 0;
}