ZeroJudge c571 - 三維偏序 解題心得( 題目 )
解題概念:cdq分治
解題方法:我們討論較小維度:
(1)一維偏序:
排序x，之後利用前綴和即可O(n)
(2)二維偏序:
排序x，利用BIT或線段樹支援區間修改、單點查詢，而我們為了方便依照x從大到小進行資料更新，也就是離線的方式，時間複雜度為O(nlogn)。
(3)三維偏序:
排序x，利用資結維護y，分治z
流程:排序z(從大到小)，接著對於z做cdq分治，利用merge sort的原理重新排序點，改成依照x排序，同時在排序的時候進行y的維護，最終時間複雜度是O(nlog^2n)。
Java參考程式碼 (有更好意見可留言於下方，謝謝!)
//Author:En Chi Tsung(欉恩祁)
//Date:2022/02/10
import java.io.*;
import java.util.*;
public class zjc571 {
public static int ret,rd,cnt;
public static final int maxn=100005;
public static int[] ans=new int[maxn];
public static int[] bit=new int[maxn];
public static Dot[] d;
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception{
final int n=readint();
d=new Dot[n];
for(int i=0;i<n;i++) {
d[i]=new Dot(readint(),readint(),readint(),i);
}
Arrays.sort(d,new Comparator<Dot>() {
public int compare(Dot f,Dot s) {
if(f.z!=s.z) return s.z-f.z;
return f.y-s.y;
}
});
int[] no=new int[n];
for(int i=0;i<n;i++) {
no[i]=i;
}
no=cdq(no);
for(int i=0;i<n;i++) {
bw.write(ans[i]+"\n");
}
bw.flush();
}
public static void update(int x,int v) {
for(int i=x;i<maxn;i+=(i&-i)) {
bit[i]+=v;
}
}
public static int query(int x) {
cnt=0;
for(int i=x;i>0;i-=(i&-i)) {
cnt+=bit[i];
}
return cnt;
}
public static int[] cdq(int[] in) {
if(in.length<=1)return in;
int mid=(in.length>>1),lp=0,rp=0;
int[] L=new int[mid];
int[] R=new int[in.length-mid];
int[] o=new int[in.length];
for(int i=0;i<mid;i++) {
L[i]=in[i];
}
for(int i=mid;i<in.length;i++) {
R[i-mid]=in[i];
}
L=cdq(L);
R=cdq(R);
while(lp<L.length&&rp<R.length) {
if(d[L[lp]].x<=d[R[rp]].x) {
o[lp+rp]=R[rp];
ans[d[R[rp]].o]+=query(100000)-query(d[R[rp]].y);
rp++;
}
else {
o[lp+rp]=L[lp];
update(d[L[lp]].y,1);
lp++;
}
}
while(lp<L.length) {
o[lp+rp]=L[lp];
update(d[L[lp]].y,1);
lp++;
}
while(rp<R.length) {
o[lp+rp]=R[rp];
ans[d[R[rp]].o]+=query(100000)-query(d[R[rp]].y);
rp++;
}
for(int i=0;i<L.length;i++) {
update(d[L[i]].y,-1);
}
return o;
}
public static int readint() throws Exception {
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
class Dot{
int x,y,z,o;
Dot(int a,int b,int c,int d){
x=a;
y=b;
z=c;
o=d;
}
}
文章標籤
全站熱搜
