# Bzoj3262 陌上花开

## 三维偏序的神方法

Posted by yjjr's blog on February 19, 2018

# 题目

## Sample Input

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1


## Sample Output

3
1
3
0
1
0
1
0
0
1


# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
int tn,n,m,t[maxn<<1],ans[maxn];
struct node{int a,b,c,s,ans;}a[maxn],p[maxn];
inline bool cmp(node a,node b){
if(a.a==b.a&&a.b==b.b)return a.c<b.c;
return a.a==b.a?a.b<b.b:a.a<b.a;
}
inline bool operator < (node a,node b){return a.b==b.b?a.c<b.c:a.b<b.b;}
inline int lowbit(int x){return x&(-x);}
void modify(int x,int num){for(int i=x;i<=m;i+=lowbit(i))t[i]+=num;}
inline int query(int x){int re=0;for(int i=x;i;i-=lowbit(i))re+=t[i];return re;}
void solve(int l,int r){
if(l==r)return;int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
sort(p+l,p+mid+1);sort(p+mid+1,p+r+1);
int i=l,j=mid+1;
while(j<=r){
while(i<=mid&&p[i].b<=p[j].b){modify(p[i].c,p[i].s);i++;}
p[j].ans+=query(p[j].c);j++;
}
rep(j,l,i-1)modify(p[j].c,-p[j].s);
}
int main()
{
sort(a+1,a+1+tn,cmp);int cnt=0;
rep(i,1,tn){
cnt++;
if(a[i].a!=a[i+1].a||a[i].b!=a[i+1].b||a[i].c!=a[i+1].c){
p[++n]=a[i];
p[n].s=cnt;
cnt=0;
}
}
solve(1,n);
rep(i,1,n)ans[p[i].ans+p[i].s-1]+=p[i].s;
rep(i,0,tn-1)printf("%d\n",ans[i]);
return 0;
}