洛谷P3810 陌上花开 CDQ分治(三维偏序)

时间：2024-01-14 16:08:56

好，这是一道三维偏序的模板题

当然没那么简单.....

首先谴责洛谷一下：可怜的陌上花开的题面被无情的消灭了：

这么好听的名字#(滑稽)

那么我们看了题面后就发现：这就是一个三维偏序。只不过ans不加在一起，而是加在每朵花内部。

很裸的一道CDQ分治，CDQ一维，sort一维，TreeArray一维，然后就爆0了......

把cmp函数改完备之后还是爆0，为什么呢？

看一下这一组样例：

5 3

1 3 3

3 3 3

3 3 3

3 3 3

3 3 3

看得出来正确答案是1 0 0 0 4

但是我们的程序无情的输出了1 1 1 1 1

这表明了什么？要去重！

就用类似离散化的方式去重，然后就——爆0了！

......

然后发现是代码里一个小细节写错了，害得我调了一晚上...

上代码。

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int N = ,K = ;

 struct Node

 {

     int a,b,c,ans,sum;

     bool operator==(const Node &x)const

     {

         return (this->a==x.a)&&(this->b==x.b)&&(this->c==x.c);

     }

 }node[N];

 bool cmp_a(Node x,Node y) /// !!!!

 {

     if(x.a!=y.a)return x.a<y.a;

     if(x.b!=y.b)return x.b<y.b;

     return x.c<y.c;

 }

 bool cmp_b(Node x,Node y)

 {

     if(x.b!=y.b)return x.b<y.b;

     return x.c<y.c;

 }

 int lowbit(int x){return x&(-x);}

 int TA[K],n,k;

 void add(int x,int a)

 {

     if(!x) return;

     for(int i=x;i<=k;i+=lowbit(i)) TA[i]+=a;

     return;

 }

 int getsum(int x)

 {

     if(!x)return ;int ans=;

     for(int i=x;i>;i-=lowbit(i)) ans+=TA[i];

     return ans;

 }

 void merge(int l,int r)

 {

     //printf("merge:%d %d\n",l,r);

     int mid=(l+r)>>;

     sort(node+l,node+mid+,cmp_b);

     sort(node+mid+,node+r+,cmp_b);

     int i=l,j=mid;

     while(j<r)

     {

         j++;

         while(node[i].b<=node[j].b&&i<=mid)

             add(node[i].c,node[i].sum),i++;

         node[j].ans+=getsum(node[j].c);//printf("node[%d].ans+=%d\n",j,getsum(node[j].c));

     }

     for(j=l;j<i;j++) add(node[j].c,-*node[j].sum);/// !!!!

     //fill(TA,TA+K,0);

     return;

 }

 void CDQ(int l,int r)

 {

     if(l==r) return;

     int mid=(l+r)>>;

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

     merge(l,r);

     return;

 }

 int ans[N];

 int main()

 {

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

     for(int i=;i<=n;i++) scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);

     sort(node+,node+n+,cmp_a);

     int t=,c=;

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

     {

         if(node[i]==node[i-])

         {

             c++;

         }

         else

         {

             node[++t]=node[i-];

             node[t].sum=c;

             c=;

         }

     }

     //for(int i=1;i<=t;i++) printf("%d %d %d %d\n",node[i].a,node[i].b,node[i].c,node[i].sum);

     CDQ(,t);

     sort(node+,node++t,cmp_a);

     //for(int i=1;i<=t;i++) printf("%d ",node[i].ans);printf("\n");

     for(int i=;i<=t;i++) ans[node[i].ans+node[i].sum-]+=node[i].sum;///这里加上去掉的重复桦

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

     return ;

 }

AC代码：

第一次写CDQ，繁琐的细节好多...

相关文章