欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P3810(陌上花开)(三维偏序,cdq分治)

程序员文章站 2022-05-14 18:41:51
...

洛谷P3810(陌上花开)(三维偏序,cdq分治)

题目链接:传送门

思路:

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

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

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

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

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

  • li,jml\le i,j\le m
  • lim  and  m+1jrl\le i\le m ~~and~~m+1\le j\le r​
  • $ m+1\le i,j\le r​$

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

对于第二种情况的偏序对,我们可以让左区间按bib_i从小到大排序,右区间从小到大排序。遍历右区间的所有元素,假设为第ii个元素,那么找到左区间满足bjb_j小于等于 bib_ijj,统计其cjc_j小等于cic_i的数量。但是右区间我们对b进行了排序操作,所以其bib_i是非递减的,所以我们可以使用双指针O(n)O(n)来统计, 树状数组来维护cjc_j

注意:因为树状数组是重复使用的,所以每次我们要执行之前添加cjc_j的逆过程来清空树状数组。

代码:

#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;
}