洛谷P3810（陌上花开）（三维偏序，cdq分治）

题目链接：传送门

思路：

PS：cdq是一种思路，因为最早是被陈丹琦引入国内的，所以就叫 cdq 分治了。

本题中的三维偏序可以取等号，所以需要注意（a,b,c）相等的情况。这时不能定义顺序，所以我们记录该元组的数量即可。

对于每个元组，我们先记录严格小于(a,b,c)元组的数量，再加上与之相等元组的数量就是这个小于等于指这个元组答案。

所以我们先将所有元组按a，b，c分别为第一，第二，第三关键字进行从小到大排序。那么对于第i个元组，严格小于这个元素的元组只会在 $i$i 左边。然后进行cdq分治。

对于区间 $[l,r]$[l,r] 的计算，假设区间中点为m，对于每个偏序对i，j分为三种情况。

• $l\le i,j\le m$l≤i,j≤m
• $l\le i\le mandm+1\le j\le r$l≤i≤m  and  m+1≤j≤r​
• $m+1\le i,j\le r$m+1≤i,j≤r​

那么第一种情况的偏序对，我们用 $cdq(l,m)$cdq(l,m)来计算，第三种情况的偏序对我们用 $cdq(m+1,r)$cdq(m+1,r)来计算。

对于第二种情况的偏序对，我们可以让左区间按 $b_i$bi​从小到大排序，右区间从小到大排序。遍历右区间的所有元素，假设为第 $i$i个元素，那么找到左区间满足 $b_j$bj​小于等于 $b_i$bi​的 $j$j，统计其 $c_j$cj​小等于 $c_i$ci​的数量。但是右区间我们对b进行了排序操作，所以其 $b_i$bi​是非递减的，所以我们可以使用双指针 $O\left(n\right)$O(n)来统计， 树状数组来维护 $c_j$cj​。

注意：因为树状数组是重复使用的，所以每次我们要执行之前添加 $c_j$cj​的逆过程来清空树状数组。

代码：

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=1e5+20;
int MXN;
int bt[200005],f[N];
int lowbit(int k)
{
    return k&-k;
}
void modify(int k,int cnt)
{
    while(k<=MXN)
    {
        bt[k]+=cnt;
        k+=lowbit(k);
    }
}
int getpre(int k)
{
    int sum=0;
    while(k)
    {
        sum+=bt[k];
        k-=lowbit(k);
    }
    return sum;
}
struct node{
int a,b,c,cnt,sum;
}t[N];//用来保证 a不同
bool cmp(const node &a,const node &b)
{
    if(a.a!=b.a) return a.a<b.a;
    if(a.b!=b.b) return a.b<b.b;
    return a.c<b.c;
}
bool cmpb(const node &a,const node &b)
{
    return a.b<b.b;
}
void cdq(int l,int r)
{
    if(l==r) return ;
    int m=(l+r)>>1;
    cdq(l,m);
    cdq(m+1,r);
    sort(t+l,t+m+1,cmpb);
    sort(t+m+1,t+r+1,cmpb);
    int p=l-1;
    for(int i=m+1;i<=r;++i){
        //把所有<=t[i].b的元素全加
        while(p+1<=m&&t[p+1].b<=t[i].b){
            ++p;
            modify(t[p].c,t[p].cnt);
        }
        t[i].sum+=getpre(t[i].c);
    }
    for(int i=l;i<=p;++i) modify(t[i].c,-t[i].cnt);
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int n;
    cin>>n>>MXN;
    for(int i=1;i<=n;++i)
    {
        int a,b,c;
        cin>>t[i].a>>t[i].b>>t[i].c;
        t[i].cnt=1;
        t[i].sum=0;
    }
    int last=0;
    sort(t+1,t+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        if(!last) {
            t[++last]=t[i];
        }
        else if( t[last].a==t[i].a && t[last].b==t[i].b &&t[last].c==t[i].c )
            t[last].cnt++;
        else
            t[++last]=t[i];
    }

    cdq(1,last);

    for(int i=1;i<=last;++i) t[i].sum+=t[i].cnt;
    for(int i=1;i<=last;++i) f[t[i].sum]+=t[i].cnt;
    for(int i=1;i<=n;++i) cout<<f[i]<<endl;
    return 0;
}