@Junlier
2018-10-30T16:11:30.000000Z
字数 2227
阅读 1697
知识点总结
阅读体验:https://zybuluo.com/Junlier/note/1326395
身为一个资深菜鸡
分治一开始学了一晚上,后来某一天又复习了一晚上(和重新学一样。。。)
现如今才发现自己还有这个坑没有填。。。于是来填坑了。。。
就是对于问题一层一层分治达到可做状态(懵逼吧)
PS:以下面题目里的三维偏序洛谷模板为准。。。
都做过二维偏序吧。。。
有一种做法是第一维排序,第二维树状数组查询前缀和对吧(或者第二维归并)
我们考虑把二维偏序拓展到三维偏序
还是考虑第一维排序,第二维则归并排序,第三维我们再套树状数组来解决
那么具体怎么做呢?
把第一位直接在最外层排序一遍,那么是有序的了对吧
考虑对第二维进行归并,考虑怎么让其帮助第三维统计呢
(PS:这里笔者刚学的时候一直不是很明白,所以希望自己讲仔细一点。。。)
首先思考归并排序是一个怎样的过程,先递归子任务,让左一半和右一半有序,然后直接插排
我们可以借助归并排序这个左右都变得有序的阶段
很显然这个时候左边一段和右边一段是按有序的,那么我们直接考虑左边对右边的贡献
也就是说,左边的肯定是比右边的小的,然后可以在对进行插入排序的时候用树状数组统计
以为下标,为权值构一棵树状数组,每次把左边的插入,从右边在树状数组中统计
仔细思考一下,很难马上理解,但应该对你有所帮助
可以结合代码看一下(虽然我压行。。。)
#include<bits/stdc++.h>
#define il inline
#define rg register
#define ldb double
#define lst long long
#define rgt register int
#define N 100050
using namespace std;
const int Inf=1e9;
il int read()
{
rgt s=0,m=0;rg char ch=getchar();
while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int n,K,tot;
int sum[N<<1],ans[N];
struct LJL{
int a,b,c,num,siz;
il int operator !=(const LJL &y)const
{
return a!=y.a||b!=y.b||c!=y.c;
}
}ljl[N],tmp[N];
il int cmp(const LJL &x,const LJL &y)
{//按(a,b,c)排序
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;
}
il void Upd(int loc,int x){for(;loc<=K;loc+=(loc&(-loc)))sum[loc]+=x;}
il int Query(int loc){rgt ret=0;for(;loc>=1;loc-=(loc&(-loc)))ret+=sum[loc];return ret;}
//树状数组部分,打的时候很舒服,看起来般般子
void CDQ(int L,int R)
{
if(L==R)return;rgt mid=(L+R)>>1;
CDQ(L,mid),CDQ(mid+1,R);//归并
rgt i=L,j=mid+1,p=L;
while(i<=mid&&j<=R)
if(ljl[i].b<=ljl[j].b)Upd(ljl[i].c,ljl[i].siz),tmp[p++]=ljl[i++];
else tmp[p]=ljl[j],tmp[p++].num+=Query(ljl[j++].c);
while(i<=mid)Upd(ljl[i].c,ljl[i].siz),tmp[p++]=ljl[i++];
while(j<=R)tmp[p]=ljl[j],tmp[p++].num+=Query(ljl[j++].c);
for(rgt i=L;i<=mid;++i)Upd(ljl[i].c,-ljl[i].siz);
for(rgt i=L;i<=R;++i)ljl[i]=tmp[i];
}
int main()
{
n=read(),K=read();
for(rgt i=1;i<=n;++i)
tmp[i]=(LJL){read(),read(),read()};
sort(tmp+1,tmp+n+1,cmp);
for(rgt i=1;i<=n;++i)
{
if(tmp[i]!=tmp[i-1])ljl[++tot]=tmp[i];
++ljl[tot].siz;
}
CDQ(1,tot);
for(rgt i=1;i<=n;++i)ans[ljl[i].num+ljl[i].siz]+=ljl[i].siz;
for(rgt i=1;i<=n;++i)printf("%d\n",ans[i]);return 0;
return 0;
}
上面那些BZOJ都有。。。可以各大OJ多倍经验