洛谷 P3810 【模板】三维偏序（陌上花开） (cdq分治模板)

在solve(L,R)中，需要先分治solve两个子区间，再计算左边区间修改对右边区间询问的贡献。

注意，计算额外的贡献时，两子区间各自内部的顺序变得不再重要（不管怎么样左边区间的都发生在右边之前），于是就少了一维

https://www.lydsy.com/JudgeOnline/problem.php?id=3262

https://www.luogu.org/problemnew/show/P3810

此题每个操作既是修改又是查询

对于此题，先按一维排序，在solve(L,R)中先solve两个子区间，然后把L到R的操作按二维排序（由于cdq分治类似归并的特性此时两个子区间内部二维都是有序的，可以直接二路归并），然后就是一个对二、三维求逆序对的过程（只不过只有归并前在第一个区间内的修改生效，归并前在第二个区间内的查询要更新答案）

可以记一下每个元素在按第一维排序后的编号(以下代码中q[i].num)，来判断它归并前是哪个区间里的

注意：此题第一维相同的实际并不存在顺序关系，理应同时处理然后同时计算贡献，但排序后它们间总是要存在一个特定顺序的，所以要加一些奇怪的特判

具体的话：首先一开始排序的时候三个关键字都要依次考虑（而不是只考虑第一维），这样可以保证排序后大部分情况下后面的不会对前面产生贡献

上面还漏考虑了完全相等的三元组，如果它们存在则后面也会对前面产生贡献。因此只要在开始solve前补上这些后面对前面产生的贡献即可

归并可以简化为

merge(q+lp,q+mid+,q+mid+,q+rp+,tmp+lp);

copy(tmp+lp,tmp+rp+,q+lp);

或

inplace_merge(q+lp,q+mid+,q+rp+);

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 struct Q

 {

     int a,b,c,ans,num;

 }q[],tmp[];

 int n,k;

 bool c1(const Q &a,const Q &b)    {return a.a<b.a||(a.a==b.a&&a.b<b.b)||(a.a==b.a&&a.b==b.b&&a.c<b.c);}

 bool operator<(const Q &a,const Q &b)    {return a.b<b.b||(a.b==b.b&&a.num<b.num);}

 bool operator==(const Q &a,const Q &b)    {return a.a==b.a&&a.b==b.b&&a.c==b.c;}

 int dat[];

 const int N=;

 #define lowbit(x) ((x)&(-x))

 void addx(int pos,int d)

 {

     for(;pos<=N;pos+=lowbit(pos))    dat[pos]+=d;

 }

 int sum(int pos)

 {

     int ans=;

     for(;pos>;pos-=lowbit(pos))    ans+=dat[pos];

     return ans;

 }

 int num[];

 void solve(int lp,int rp)

 {

     if(lp==rp)    return;

     int mid=lp+(rp-lp)/;

     solve(lp,mid);solve(mid+,rp);

     int k=lp-,i,j;

     for(i=lp,j=mid+;i<=mid&&j<=rp;)

     {

         ++k;

         if(q[i]<q[j])    tmp[k]=q[i++];

         else    tmp[k]=q[j++];

     }

     while(i<=mid)    tmp[++k]=q[i++];

     while(j<=rp)    tmp[++k]=q[j++];

     for(i=lp;i<=rp;i++)    q[i]=tmp[i];

     for(i=lp;i<=rp;i++)

     {

         if(q[i].num<=mid)    addx(q[i].c,);

         else    q[i].ans+=sum(q[i].c);

     }

     for(i=lp;i<=rp;i++)

         if(q[i].num<=mid)

             addx(q[i].c,-);

 }

 int main()

 {

     int i,j,t,tt=;

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

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

     sort(q+,q+n+,c1);

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

     {

         tt++;

         if(i==n||!(q[i]==q[i+]))

         {

             for(j=i-tt+,t=tt-;j<=i;j++)    q[j].ans+=t,--t;

             tt=;

         }

     }

     for(i=;i<=n;i++)    q[i].num=i;

     solve(,n);

     for(i=;i<=n;i++)    num[q[i].ans]++;

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

     return ;

 }

来看看cdq分治的限制

1.题目允许离线操作
2.修改操作对询问的贡献独立，且修改之间互不影响
3.修改对答案的贡献是确定的，与判定标准无关

巴特西

洛谷 P3810 【模板】三维偏序（陌上花开） (cdq分治模板)

最新文章

热门文章