首页 > 代码库 > BZOJ 3262: 陌上花开 [CDQ分治 三维偏序]
BZOJ 3262: 陌上花开 [CDQ分治 三维偏序]
Description
有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
Input
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性
Output
包含N行，分别表示评级为0...N-1的每级花的数量。
$fuck$太坑了！！！！！！！！！
各种修改比较操作各种修改细节最后发现是因为我去重之后把$n$改变了然而人家输出需要原来的$n$!!!!!!!!!!!!!!!!!
裸的三维偏序
$a$排序，$b$ $CDQ$分治，$c$树状数组
注意需要去重
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N=2e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,maxVal;struct Operation{ int a,b,c,w; int f; bool operator <(const Operation &r)const{ //return a<r.a || (a==r.a&&b<r.b) || (a==r.a&&b==r.b&&c<r.c); return (a==r.a&&b==r.b) ? c<r.c : (a==r.a?b<r.b:a<r.a); }}a[N],t[N];int c[N];inline int lowbit(int x){return x&-x;}inline void add(int p,int v){for(;p<=maxVal;p+=lowbit(p)) c[p]+=v;}inline int sum(int p){ int re=0; for(;p;p-=lowbit(p)) re+=c[p]; return re;}int ans[N];void CDQ(int l,int r){ if(l==r) return; int mid=(l+r)>>1; CDQ(l,mid);CDQ(mid+1,r); int i=l,j=mid+1,p=l; while(i<=mid||j<=r){ if(j>r||(i<=mid&&a[i].b<=a[j].b)) add(a[i].c,a[i].w),t[p++]=a[i++]; else a[j].f+=sum(a[j].c),t[p++]=a[j++]; } for(int i=l;i<=mid;i++) add(a[i].c,-a[i].w); for(int i=l;i<=r;i++) a[i]=t[i];}int main(){ freopen("in","r",stdin); n=read();maxVal=read(); for(int i=1;i<=n;i++) a[i].a=read(),a[i].b=read(),a[i].c=read(),a[i].w=1; sort(a+1,a+1+n); int p=1; for(int i=2;i<=n;i++){ if(a[i].a==a[p].a&&a[i].b==a[p].b&&a[i].c==a[p].c) a[p].w++; else a[++p]=a[i]; } int nnnnn=n; n=p; CDQ(1,n); for(int i=1;i<=n;i++) ans[a[i].f+a[i].w-1]+=a[i].w; for(int i=0;i<=nnnnn-1;i++) printf("%d\n",ans[i]);}
BZOJ 3262: 陌上花开 [CDQ分治 三维偏序]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。