bzoj3262: 陌上花开 三维偏序cdq分治

时间：2023-03-10 05:25:25
bzoj3262: 陌上花开 三维偏序cdq分治

三维偏序裸题，cdq分治时，左侧的x一定比右侧x小，然后分别按y排序，对于左侧元素按y大小把z依次插入到树状数组里，其中维护每个左侧元素对右侧元素的贡献，在bit查询即可

/**************************************************************

    Problem: 3262

    User: walfy

    Language: C++

    Result: Accepted

    Time:3844 ms

    Memory:28640 kb

****************************************************************/

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define Max(a,  b) ((a)>(b)?(a):(b))

#define Min(a,  b) ((a)<(b)?(a):(b))

#define fio ios::sync_with_stdio(false);cin.tie(0)

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

using namespace std;

const double eps=1e-8;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=1000000+10,maxn=50000+10,inf=0x3f3f3f3f;

struct node{

    int x,y,z,w,ans;

    bool operator <(const node &rhs)const{

        return x<rhs.x || x==rhs.x&&y<rhs.y ||x==rhs.x&&y==rhs.y&&z<rhs.z;

    }

}a[N];

inline bool cmp(node a,node b){return a.y<b.y||a.y==b.y&&a.z<b.z||a.y==b.y&&a.z==b.z&&a.x<b.x;}

struct BIT{

    int sum[N];

    void add(int i,int v)

    {

        for(;i<N;i+=i&(-i))sum[i]+=v;

    }

    int query(int i)

    {

        int ans=0;

        for(;i;i-=i&(-i))ans+=sum[i];

        return ans;

    }

}b;

int num[N];

void cdq(int l,int r)

{

    if(l==r){a[l].ans+=a[l].w-1;return ;}

    int m=(l+r)>>1;

    cdq(l,m);cdq(m+1,r);

    sort(a+l,a+m+1,cmp);sort(a+m+1,a+r+1,cmp);

    int now=l;

    for(int i=m+1;i<=r;i++)

    {

        while(now<=m&&a[now].y<=a[i].y)b.add(a[now].z,a[now].w),now++;

        a[i].ans+=b.query(a[i].z);

    }

    for(int i=l;i<now;i++)

        b.add(a[i].z,-a[i].w);

}

int main()

{

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)

        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z),a[i].ans=1;

    sort(a+1,a+1+n);

    int cnt=0;

    for(int i=1;i<=n;i++)

    {

        if(i!=1&&a[i].x==a[i-1].x&&a[i].y==a[i-1].y&&a[i].z==a[i-1].z)a[cnt].w++;

        else a[++cnt]=a[i],a[cnt].w=1;

    }

    cdq(1,cnt);

    sort(a+1,a+1+cnt);

    for(int i=1;i<=cnt;i++)num[a[i].ans]+=a[i].w;

    for(int i=1;i<=n;i++)printf("%d\n",num[i]);

    return 0;

}

/********************

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

********************/

相关文章