天天看點

【模闆】三維偏序(陌上花開)

CDQ分治求解三維偏序。

1、首先三關鍵字排序,保證接下來\(i\)的可行解一定在\([1,i-1]\)中。

2、再對第二關鍵字做歸并排序,保證滿足\(a_j<a_i\)的前提下,實作\(b_j<b_i\)。合并時有兩個區間,\(j<i\),\(j\)在\([l,mid]\)中,\(i\)在\([mid+1,r]\)中,由于前一次對三關鍵字的排序,使得左區間所有\(a\)小于等于右區間所有\(a\),是以在歸并維護答案時,無需顧忌\(a\)的情況,靠雙指針來保證\(b\)有序,然後同時統計\(c\)的答案即可。

3、歸并時雙指針與樹狀數組維護第三關鍵字對答案的貢獻,注意重複三維點的情況。