偏序問題就是一個元素有若干屬性，然后統計所有屬性都有序的數對個數。

對于此類問題，思路是先消到一維，再統計答案。

1、二位偏序

例題：逆序對

其實在開始 \(i < j\) 這一維度就已經排好序了，現在剩下 \(a_i\) 這一維，發現可以對樹狀數組上 \(a_i\) 這個點加一，\(query(a_i)\) 就是 \(j < i\) 且 \(a_j \le a_i\)，那么 \(i - query(a_i)\) 就是答案。

考慮這樣做是對值域開樹狀數組，明顯開不下，怎么辦捏？

那就先對 \(a_i\) 排序，然后用樹狀數組存 \(i\) 的維度，這樣是能開下的。

復雜度 \(O(nlogn)\)

2、三位偏序

例題：陌上開花

先排序，消除一維，然后 CDQ 分治，每次分治，只考慮前半部分對后半部分的貢獻，用后半部分查詢，統計還是用樹狀數組。

復雜度 \(O(nlog^2n)\)

CDQ分治前往下一篇