淺談偏序問題

所謂偏序問題就是多限制條件的元素統計問題。

看起來好像很難了解的樣子？

比如一維偏序，就是有一種限制條件。

其實這個例子比較難舉。舉個排序的例子吧。

現在給出有一個亂序數列，請将其按從大到小的順序排序。

這題的權值就是一個限制條件。......好牽強。

比如二維偏序。就是兩種限制條件。

比如逆序對。位置是一個限制，權值是一個限制。

比如三維偏序就是三種限制條件。比如 有N個女士去參加舞會。每個女士有三個值a[i],b[i],c[i]。如果一位女士發現有其它女士的這三個值都比自己高的話就會去跳樓.求有多少跳樓的女士。

那麼偏序問題如何解決呢？

大體遵循如下規則：

一維就排序。

二維的話，先排序定一維。然後再采取措施解決下一維。

三維的話，需要CDQ分治。

差不多加一維就加一個log