经典的三位偏序经 (mo) 典(ban)题,
一维排序, 二维 CDQ 分治, 3 维 BIT
- Code
- #include <cstdio>
- #include <algorithm>
- #define lowbit(x) ((x)&(-x))
- #define N 100010
- using namespace std;
- inline int read(){
- int x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
- return x*f;
- }
- struct flower{
- int a,b,c,w,s;
- flower(){a=b=c=w=s=0;}
- friend bool operator <(flower x,flower y){
- return (x.a==y.a&&x.b==y.b)?(x.c<y.c):((x.a==y.a)?x.b<y.b:x.a<y.a);
- }
- friend bool operator ==(flower x,flower y){
- return (x.a==y.a&&x.b==y.b&&x.c==y.c);
- }
- void rd(){a=read(),b=read(),c=read(),w=1;}
- }A[N],tmp[N];
- int n,mx,na,T[N*2],Ans[N];
- inline void Init(){
- n=read(),mx=read();
- for(int i=1;i<=n;A[i++].rd());
- sort(A+1,A+n+1);
- int p=1;
- for(int i=2;i<=n;++i) if(A[i]==A[p]) A[p].w++;else A[++p]=A[i];// 去重
- na=n,n=p;
- }
- void add(int x,int v){for(;x<=mx;x+=lowbit(x)) T[x]+=v;}
- int sum(int x){int r=0;for(;x;x-=lowbit(x)) r+=T[x];return r;}
- inline void solve(int l,int r){
- if(l==r) return;
- int m=(l+r)>>1;
- solve(l,m),solve(m+1,r);
- int p=l,q=m+1,cnt=l;
- while(p<=m||q<=r)
- if(q>r||(p<=m&&A[p].b<=A[q].b)) add(A[p].c,A[p].w),tmp[cnt++]=A[p++];
- else A[q].s+=sum(A[q].c),tmp[cnt++]=A[q++];
- for(int i=l;i<=m;++i) add(A[i].c,-A[i].w);// 清空 BIT
- for(int i=l;i<=r;++i) A[i]=tmp[i];
- }
- int main(){
- Init();
- solve(1,n);
- for(int i=1;i<=n;++i) Ans[A[i].s+A[i].w-1]+=A[i].w;
- for(int i=0;i<na;printf("%d\n",Ans[i++]));
- return 0;
- }
[BZOJ3262]陌上花开(CDQ 分治)
来源: http://www.bubuko.com/infodetail-2614868.html