陌上花开（三维偏序）（cdq分治）

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3262

其实就是三位偏序的模板，cdq分治入门题。

学习cdq分治请看__stdcall大佬的博客：传送门

排序来维护第一层，cdq维护一层，树状数组维护一层，然后就没有啦qwqwq

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,k,cnt;
int ans[MAXN],tree[MAXN<<1];
struct Node{int a,b,c,sum,ans;}node[MAXN],now[MAXN];
inline bool cmp1(struct Node x,struct Node y)
{
    if(x.a!=y.a) return x.a<y.a;
    if(x.b!=y.b) return x.b<y.b;
    return x.c<y.c;
}
inline bool cmp2(struct Node x,struct Node y)
{
    if(x.b!=y.b) return x.b<y.b;
    return x.c<y.c;
}
inline bool check(struct Node x,struct Node y)
{
    if((x.a==y.a)&&(x.b==y.b)&&(x.c==y.c)) return true;
    else return false;
}
inline void add(int x,int val)
{
    for(int i=x;i<=k;i+=(i&-i))
        tree[i]+=val;
}
inline int query(int x)
{
    int cur_ans=0;
    for(int i=x;i;i-=(i&-i))
        cur_ans+=tree[i];
    return cur_ans;
}
inline void cdq(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    sort(&now[l],&now[mid+1],cmp2);
    sort(&now[mid+1],&now[r+1],cmp2);
    int i=l;
    for(int j=mid+1;j<=r;j++)
    {   
        while(i<=mid&&now[i].b<=now[j].b)
            add(now[i].c,now[i].sum),i++;
        now[j].ans+=query(now[j].c);
    }
    for(int j=l;j<i;j++) add(now[j].c,-now[j].sum);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);
    sort(node+1,node+1+n,cmp1);
    for(int i=1;i<=n;i++)
    {
        if(check(node[i],node[i-1])) now[cnt].sum++;
        else cnt++,now[cnt]=node[i],now[cnt].sum++;
    }
    cdq(1,cnt);
    for(int i=1;i<=cnt;i++) ans[now[i].ans+now[i].sum-1]+=now[i].sum;
    for(int i=0;i<n;i++) printf("%d
",ans[i]);
    return 0;
}