M_sea

BZOJ3262 陌上花开
BZOJLuogu分析广告:hbx的题解求三维偏序,用CDQ分治降至二维。再排个序,降为一维。再用树状数组维护一下...
扫描右侧二维码阅读全文
18
2018/12

BZOJ3262 陌上花开

BZOJ

Luogu

分析

广告:hbx的题解

求三维偏序,用CDQ分治降至二维。

再排个序,降为一维。

再用树状数组维护一下,就能解决三维偏序。

细节:

  1. 去重。
  2. 统计答案时,要加上重复的。
  3. 不能memset掉树状数组,会T飞。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;
const int MAXK=200000+10;

struct node {
    int x,y,z,w,ans;
    bool operator <(const node& rhs) const {
        if (x!=rhs.x) return x<rhs.x;
        if (y!=rhs.y) return y<rhs.y;
        return z<rhs.z;
    }
    bool operator ==(const node& rhs) const {
        return x==rhs.x&&y==rhs.y&&z==rhs.z;
    }
} a[MAXN];

int n,k;

inline int cmp(node A,node B) {
    if (A.y!=B.y) return A.y<B.y;
    return A.z<B.z;
}

int c[MAXK];
inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) { while (x<=k) c[x]+=y,x+=lowbit(x); }
inline int sum(int x) { int rt=0; while (x) rt+=c[x],x-=lowbit(x); return rt; }

inline void CDQ(int L,int R) {
    if (L==R) return;
    int mid=(L+R)>>1;
    CDQ(L,mid); CDQ(mid+1,R);
    sort(a+L,a+mid+1,cmp); sort(a+mid+1,a+R+1,cmp);
    int i=L;
    for (re int j=mid+1;j<=R;++j) {
        while (i<=mid&&a[i].y<=a[j].y) {
            add(a[i].z,a[i].w);
            ++i;
        }
        a[j].ans+=sum(a[j].z);
    }
    for (re int j=L;j<i;++j) add(a[j].z,-a[j].w); //细节三
}

int ans[MAXN];

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) a[i].x=read(),a[i].y=read(),a[i].z=read();
    sort(a+1,a+n+1); int tmp=0;
    for (re int i=1;i<=n;++i) { //细节一
        if (a[i]==a[i-1]) ++a[tmp].w;
        else a[++tmp]=a[i],a[tmp].w=1;
    }
    int N=n,n=tmp;
    CDQ(1,n);
    for (re int i=1;i<=n;++i) ans[a[i].ans+a[i].w]+=a[i].w; //细节二
    for (re int i=1;i<=N;++i) printf("%d\n",ans[i]);
    return 0;
}
最后修改:2019 年 01 月 22 日 01 : 27 PM

发表评论