[BZOJ3262] 陌上花开

本文主要是介绍[BZOJ3262] 陌上花开，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

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

题目大意

$给定三维点对(x_i,y_i,z_i)若两个点对存在x_i<=x_j,y_i<=y_j,z_i<=z_j则称点i<j,询问每个点前有多少点$

题解

三维偏序
cdq分治
我们对三维按x为第一关键字,y为第二关键字.z为第三关键字排序
这样我们得到的每个点前面的点x那维一定小于等于自己
然后我们分治y那维,这个过程类似归并排序的过程
对于我们分治时相邻的区间,我们把两个区间内的点只看y那维合并成一个区间
对于左边的区间会对右边区间产生贡献(因为x值<=右边的任意一个)
这个贡献我们把他们的z值插进树状数组中
当右区间指针的点因为比左区间指针的点而踢出时,查询树状数组中小于等于它z值得点个数
这样就可以优化掉一位
不清楚的画图看看,注意相同的先和成一个点,插进树状数组时是sum值不是1,每次树状数组要清0

typedata=recordx,y,z,num,ans:longint; end;
vart,temp:array[0..100005]of data;bite,ans:array[0..200005]of longint;i,j,k:longint;n,m,s:longint;
procedure sort(l,r:longint);
var i,j,a,b,c:longint; d:data;
begini:=l; j:=r; a:=t[(l+r) div 2].x; b:=t[(l+r)div 2].y; c:=t[(l+r)div 2].z;repeatwhile (t[i].x<a)or((t[i].x=a)and(t[i].y<b))or((t[i].x=a)and(t[i].y=b)and(t[i].z<c)) do inc(i);while (a<t[j].x)or((t[j].x=a)and(t[j].y>b))or((t[j].x=a)and(t[j].y=b)and(t[j].z>c)) do dec(j);if not(i>j) thenbegind:=t[i]; t[i]:=t[j]; t[j]:=d;inc(i); dec(j);end;until i>j;if l<j then sort(l,j);if i<r then sort(i,r);
end;procedure update(a,b:longint);
var tt:longint;
begintt:=a;while tt<=s dobegininc(bite[tt],b);inc(tt,tt and (-tt));end;
end;function query(a:longint):longint;
var tt,sum:longint;
begintt:=a; sum:=0;while tt>0 dobegininc(sum,bite[tt]);dec(tt,tt and (-tt));end;exit(sum);
end;procedure cdq(l,r:longint);
var i,j,k,mid,len:longint;
beginif l=r then exit;mid:=(l+r)>>1;cdq(l,mid); cdq(mid+1,r);i:=l; j:=mid+1; len:=l;while (i<=mid)and(j<=r) dobeginif (t[i].y<=t[j].y)then begin update(t[i].z,t[i].num); temp[len]:=t[i]; inc(i); inc(len); continue; endelse begin inc(t[j].ans,query(t[j].z)); temp[len]:=t[j]; inc(j); inc(len); end;end;for k:=j to r dobegin inc(t[k].ans,query(t[k].z)); temp[len]:=t[k]; inc(len); end;for k:=l to mid doif k>=ithen begin temp[len]:=t[k]; inc(len); endelse update(t[k].z,-t[k].num);for i:=l to r dot[i]:=temp[i];
end;beginreadln(n,s);for i:=1 to n doreadln(t[i].x,t[i].y,t[i].z);sort(1,n); {t[i].x}m:=0; t[0].x:=0; t[0].y:=0; t[0].z:=0;for i:=1 to n dobegin t[i].ans:=0; t[i].num:=0; end;for i:=1 to n doif (t[i].x=t[i-1].x)and(t[i].y=t[i-1].y)and(t[i].z=t[i-1].z)then inc(t[m].num)else begin inc(m); t[m]:=t[i]; t[m].num:=1; end;cdq(1,m);fillchar(ans,sizeof(ans),0);for i:=1 to n doinc(ans[t[i].ans+t[i].num-1],t[i].num);for i:=0 to n-1 dowriteln(ans[i]);
end.

这篇关于[BZOJ3262] 陌上花开的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---