bzoj 3263 陌上花开（cdq分治，BIT）

 

【题意】

　　求满足Ai<=Aj,Bi<=Bj,Ci<=Cj的数对的数目。

　　

【思路】

cdq分治

借网上一句话：第一维排序，第二维cdq分治，第三维树状数组维护。

首先合并三维都是相同的项。

先按照第一维排序然后cdq分治。

定义solve(l,r)为解决区间l,r内所有询问且solve结束后区间有序，设mid=(l+r)/2，

　　1)  Solve(l,mid)

　　2)  Solve(mid+1,r)

　　//因为经过第一维排序，所以左区间的a都小于等于右区间的a。

　　3)  处理跨立影响。因为已经排过序，所以左区间的a都要小于右区间的a，因为solve后区间有序，所以左右区间都各自按照b排好了序。按照归并排序的思路，计算左区间对每一个右区间内点的贡献：处理到右区间的l2时,将所有左区间内比他的b小的加入BIT，这时候只要查询一次就可以得出左区间对l2的贡献。

　　4)  清理BIT，并按照b c大小将左右区间合并使区间有序

　 最后根据题目要求转化一下。

　 总的时间为O(nlog^2n)，bingo

【代码】

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N = *1e5+;

 struct Node {

     int a,b,c,s,ans;

 }que[N],a[N];

 bool cmp1(const Node& x,const Node& y) {

     return x.b<y.b||(x.b==y.b&&x.c<y.c);

 }

 bool cmp2(const Node& x,const Node& y) {

     if(x.a==y.a&&x.b==y.b) return x.c<y.c;

     else if(x.a==y.a) return x.b<y.b;

     else return x.a<y.a;

 }

 int n,K,C[N],ans[N];

 void add(int x,int v)

 {

     for(;x<=K;x+=x&-x) C[x]+=v;

 }

 int query(int x)

 {

     int res=;

     for(;x;x-=x&-x) res+=C[x];

     return res;

 }

 Node t[N];

 void solve(int l,int r)

 {

     if(l==r) return ;

     int mid=(l+r)>>;

     solve(l,mid) , solve(mid+,r);

     int l1=l,l2=mid+;

     while(l2<=r) {

         while(l1<=mid && que[l1].b<=que[l2].b) {

             add(que[l1].c,que[l1].s);

             l1++;

         }

         que[l2].ans+=query(que[l2].c);

         l2++;

     }

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

         add(que[i].c,-que[i].s);

     l1=l,l2=mid+; int pos=l;

     while(l1<=mid||l2<=r) {

         if(l2>r||(l1<=mid&&cmp1(que[l1],que[l2]))) t[pos++]=que[l1++];

         else t[pos++]=que[l2++];

     }

     for(int i=l;i<=r;i++) que[i]=t[i];

 }

 void read(int& x)

 {

     char c=getchar(); x=;

     while(!isdigit(c)) c=getchar();

     while(isdigit(c)) x=x*+c-'',c=getchar();

 }

 int main()

 {

     //freopen("in.in","r",stdin);

     //freopen("out.out","w",stdout);

     read(n),read(K);

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

         read(a[i].a),read(a[i].b),read(a[i].c);

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

     int cnt=,sz=;

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

         cnt++;

         if(a[i].a!=a[i+].a||a[i].b!=a[i+].b||a[i].c!=a[i+].c)

         {

             que[++sz]=a[i];

             que[sz].s=cnt;

             cnt=;

         }

     }

     solve(,sz);

     for(int i=;i<=sz;i++)

         ans[que[i].ans+que[i].s-]+=que[i].s;

     //评级为0~n-1的每级花的数量

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

         printf("%d\n",ans[i]);

     return ;

 }