luogu3810 三维偏序
先是计算f。
显然第一维排序。
然后第二维CDQ分治。
CDQ分治时用树状数组处理第三维。 具体是这样的：
显然树状数组的两个操作分别是\(add(a,b)\)和\(sum(a)\)，意义显然。
首先一样的点合并。（显然）
设和第i个点重合的点个数为\(Tot_i\)，第i个点的三维分别为\(A_i,B_i,C_i\).
然后按照第一维，第二维，第三维为第一二三个关键字升序排序。
然后CDQ分治。
CDQ分治是这样的： CDQ(l,r): CDQ(l,mid) CDQ(mid+1,r) 处理\([l,mid]\)区间对\((mid,r]\)区间的贡献。
处理贡献时可以这样做： 首先很显然\([l,mid]\)区间和\((mid,r]\)区间的第二维是有序的（保持有序可以在之后归并维护），并且左区间的第一维全部严格小于右区间的。 然后归并。 假设正在比较左区间的x点和右区间的y点。 如果\(B_x\le B_y\)，则\(add(C_x,Tot_x)\)。 否则\(f(y)+=sum(C_y)\) 注意初始化的时候千万不能把树状数组全部置为0，要把加入树状数组的一个个减回去。 前一种方法复杂度 \(O(k)\) ，后一种复杂度 \(O(m log_2 k)\) ，其中m为加进去的个数。 则初始化的总复杂度为第一种\(O(nk)\)，后一种为\(O(n log_2 n log_2 k)\) 若一开始对第三维离散化，则复杂度为\(O(n log_2^2 n)\)
/*
Author: CNYALI_LK
LANG: C++
PROG: 3810.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int n,k;
inline int read(){
char c;
int s=0;
while(!isdigit(c=getchar()));
while(isdigit(c)){s=s*10+c-'0';c=getchar();}
return s;
}
struct node{
int a,b,c,cnt;
int ans;
void init(int d){a=read();b=read();c=read();}
};
int a_cmp(node a,node b){return a.a<b.a||(a.a==b.a&&(a.b<b.b||(a.b==b.b&&a.c<b.c)));}
node a[102424],b[102424];
int ans[102424];
int c[204848];
#define lowbit(x) x&(-x)
inline void add(int x,int y){
while(x<=k){
c[x]+=y;
x+=lowbit(x);
}
}
inline int sum(int x){
int cnt=0;
while(x){
cnt+=c[x];
x^=lowbit(x);
}
return cnt;
}
inline void cdq(int l,int r){
if(l==r){a[l].ans=a[l].cnt;return;}
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
int sa=l,sb=mid+1,t=l-1;
while(sb<=r){
while(sa<=mid&&a[sa].b<=a[sb].b){
b[++t]=a[sa];
add(a[sa].c,a[sa].cnt);
++sa;
}
b[++t]=a[sb];
b[t].ans+=sum(b[t].c);
++sb;
}
for(int i=l;i<sa;++i)add(a[i].c,-a[i].cnt);
while(sa<=mid){
b[++t]=a[sa];
++sa;
}
for(int i=l;i<=r;++i)a[i]=b[i];
}
inline int same(node a,node b){return a.a==b.a&&a.b==b.b&&a.c==b.c;}
int hv[233333];
int main(){
#ifdef cnyali_lk
freopen("3810.in","r",stdin);
freopen("3810.out","w",stdout);
#endif
n=read();k=read();
for(int i=1;i<=n;++i){
b[i].init(i);
hv[b[i].c]=1;
}
sort(b+1,b+n+1,a_cmp);
int m=0,l=0;
for(int i=1;i<=k;++i)if(hv[i])hv[i]=++l;
k=l;
for(int i=1;i<=n;++i)if(same(b[i],a[m])){
++a[m].cnt;
}
else {a[++m]=b[i];a[m].cnt=1;}
for(int i=1;i<=n;++i)a[i].c=hv[a[i].c];
n^=m^=n^=m;
cdq(1,n);
for(int i=1;i<=n;++i)ans[a[i].ans]+=a[i].cnt;
for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
return 0;
}