BZOJ3262/洛谷P3810 陌上花开 分治 三维偏序 树状数组

原文链接http://www.cnblogs.com/zhouzhendong/p/8672131.html

题目传送门 - BZOJ3262

题目传送门 - 洛谷P3810

题意

  有$n$个元素,第$i$个元素有$a_i$、$b_i$、$c_i$三个属性,设$f(i)$表示满足$a_j\leq a_i$且$b_j\leq b_i$且$c_j\leq c_i$的$j$的数量。对于$d\in [0,n)$,求$f(i)=d$的数量。

  $n\leq 100000,max\{a_i,b_i,c_i|i\in[1,n]\}<=200000$

题解

  三维偏序模版题。

  CDQ分治一波。树套树也可以。

  CDQ分治思路:

    一维偏序:直接排序。

    二维偏序:树状数组。

    三维偏序:第3维套CDQ分治。

  对于第一维和第二维我们还是按照原样处理。

  对于第三维,我们考虑分治。

  首先显然要排序。

  对于一个区间$[L,R]$,首先求得$mid=\left\lfloor\frac{L+R}{2}\right\rfloor$。

  然后考虑先分治$[L,mid]$和$[mid+1,R]$。

  然后通过树状数组的做法,用左区间来更新右区间。注意树状数组的还原。

  总体来说,对于第3维,是在开始的时候保存了rank。对于第2维,是在递归的过程中归并得到了有序排列。对于第1维,由于一开始排序的时候作为了第3关键字,而归并排序具有稳定性,所以,对于第二维相同的,第三维是有序的。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
struct Node{
int x,y,z,rank,res;
void get(){
scanf("%d%d%d",&x,&y,&z),res=0;
}
}a[N],b[N];
int n,k,tree[N*2],tot[N];
bool cmp(Node a,Node b){
if (a.x!=b.x)
return a.x<b.x;
if (a.y!=b.y)
return a.y<b.y;
return a.z<b.z;
}
bool issame(Node a,Node b){
return a.x==b.x&&a.y==b.y&&a.z==b.z;
}
void sameadd(){
int tot=1,last=n;
for (int i=n-1;i>=1;i--)
if (issame(a[i],a[last]))
a[i].res+=tot++;
else
last=i,tot=1;
}
int lowbit(int x){
return x&-x;
}
void add(int x,int y){
for (;x<=k;x+=lowbit(x))
tree[x]+=y;
}
int sum(int x){
int ans=0;
for (;x>0;x-=lowbit(x))
ans+=tree[x];
return ans;
}
void CDQ(int L,int R){
if (L==R)
return;
int mid=(L+R)>>1,cnt=L;
CDQ(L,mid),CDQ(mid+1,R);
for (int i=L,l=L,r=mid+1;i<=R;i++)
if (r>R||(l<=mid&&a[l].y<=a[r].y))
b[cnt++]=a[l++];
else
b[cnt++]=a[r++];
for (int i=L;i<=R;i++){
a[i]=b[i];
if (a[i].rank<=mid)
add(a[i].z,1);
else
a[i].res+=sum(a[i].z);
}
for (int i=L;i<=R;i++)
if (a[i].rank<=mid)
add(a[i].z,-1);
}
int main(){
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
a[i].get();
sort(a+1,a+n+1,cmp);
sameadd();
for (int i=1;i<=n;i++)
a[i].rank=i;
memset(tree,0,sizeof tree);
CDQ(1,n);
memset(tot,0,sizeof tot);
for (int i=1;i<=n;i++)
tot[a[i].res]++;
for (int i=0;i<n;i++)
printf("%d\n",tot[i]);
return 0;
}

  

上一篇:NYOJ-括号配对问题 <技巧性的非栈道法>


下一篇:基于visual Studio2013解决算法导论之054图的邻接矩阵表示