[关闭]
@Junlier 2018-10-30T16:11:30.000000Z 字数 2227 阅读 1683

分治小结

知识点总结
阅读体验：https://zybuluo.com/Junlier/note/1326395
身为一个资深菜鸡
分治一开始学了一晚上，后来某一天又复习了一晚上（和重新学一样。。。）
现如今才发现自己还有这个坑没有填。。。于是来填坑了。。。

简介定义

就是对于问题一层一层分治达到可做状态（懵逼吧）

正儿八经地讲

PS：以下面题目里的三维偏序洛谷模板为准。。。
都做过二维偏序吧。。。
有一种做法是第一维排序，第二维树状数组查询前缀和对吧（或者第二维归并）
我们考虑把二维偏序拓展到三维偏序
还是考虑第一维排序，第二维则归并排序，第三维我们再套树状数组来解决
那么具体怎么做呢？

把第一位直接在最外层排序一遍，那么是有序的了对吧
考虑对第二维进行归并，考虑怎么让其帮助第三维统计呢
（PS：这里笔者刚学的时候一直不是很明白，所以希望自己讲仔细一点。。。）
首先思考归并排序是一个怎样的过程，先递归子任务，让左一半和右一半有序，然后直接插排
我们可以借助归并排序这个左右都变得有序的阶段
很显然这个时候左边一段和右边一段是按有序的，那么我们直接考虑左边对右边的贡献
也就是说，左边的肯定是比右边的小的，然后可以在对进行插入排序的时候用树状数组统计
以为下标，为权值构一棵树状数组，每次把左边的插入，从右边在树状数组中统计

仔细思考一下，很难马上理解，但应该对你有所帮助
可以结合代码看一下(虽然我压行。。。)

  1. #include<bits/stdc++.h>
  2. #define il inline
  3. #define rg register
  4. #define ldb double
  5. #define lst long long
  6. #define rgt register int
  7. #define N 100050
  8. using namespace std;
  9. const int Inf=1e9;
  10. il int read()
  11. {
  12.     rgt s=0,m=0;rg char ch=getchar();
  13.     while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
  14.     while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  15.     return m?-s:s;
  16. }
  18. int n,K,tot;
  19. int sum[N<<1],ans[N];
  20. struct LJL{
  21.     int a,b,c,num,siz;
  22.     il int operator !=(const LJL &y)const
  23.         {
  24.             return a!=y.a||b!=y.b||c!=y.c;
  25.         }
  26. }ljl[N],tmp[N];
  27. il int cmp(const LJL &x,const LJL &y)
  28. {//按(a,b,c)排序
  29.     if(x.a!=y.a)return x.a<y.a;
  30.     if(x.b!=y.b)return x.b<y.b;
  31.     return x.c<y.c;
  32. }
  33. il void Upd(int loc,int x){for(;loc<=K;loc+=(loc&(-loc)))sum[loc]+=x;}
  34. il int Query(int loc){rgt ret=0;for(;loc>=1;loc-=(loc&(-loc)))ret+=sum[loc];return ret;}
  35. //树状数组部分，打的时候很舒服，看起来般般子
  37. void CDQ(int L,int R)
  38. {
  39.     if(L==R)return;rgt mid=(L+R)>>1;
  40.     CDQ(L,mid),CDQ(mid+1,R);//归并
  41.     rgt i=L,j=mid+1,p=L;
  42.     while(i<=mid&&j<=R)
  43.         if(ljl[i].b<=ljl[j].b)Upd(ljl[i].c,ljl[i].siz),tmp[p++]=ljl[i++];
  44.         else tmp[p]=ljl[j],tmp[p++].num+=Query(ljl[j++].c);
  45.     while(i<=mid)Upd(ljl[i].c,ljl[i].siz),tmp[p++]=ljl[i++];
  46.     while(j<=R)tmp[p]=ljl[j],tmp[p++].num+=Query(ljl[j++].c);
  47.     for(rgt i=L;i<=mid;++i)Upd(ljl[i].c,-ljl[i].siz);
  48.     for(rgt i=L;i<=R;++i)ljl[i]=tmp[i];
  49. }
  51. int main()
  52. {
  53.     n=read(),K=read();
  54.     for(rgt i=1;i<=n;++i)
  55.         tmp[i]=(LJL){read(),read(),read()};
  56.     sort(tmp+1,tmp+n+1,cmp);
  57.     for(rgt i=1;i<=n;++i)
  58.     {
  59.         if(tmp[i]!=tmp[i-1])ljl[++tot]=tmp[i];
  60.         ++ljl[tot].siz;
  61.     }
  62.     CDQ(1,tot);
  63.     for(rgt i=1;i<=n;++i)ans[ljl[i].num+ljl[i].siz]+=ljl[i].siz;
  64.     for(rgt i=1;i<=n;++i)printf("%d\n",ans[i]);return 0;
  65.     return 0;
  66. }

给一些题目

上面那些BZOJ都有。。。可以各大OJ多倍经验

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注