多维偏序

前言


由于之前没接触过这类偏序问题,现在暂且只是简单了解和总结,网络赛做了一道用树状数组解决的二维偏序,$CDQ$分治也还不了解,之后题目做多了,应该慢慢就会掌握了~

定义


一般情况下,我们比较一个数大小,就是$a_{i}>a_{j}$即可,

而在上升子序列中,当$i>j$并且$a_{i}>a_{j}$的时候,才可以认为i这位的数大于j这位的数。

这就是一个二维偏序。

类似的,有$n$个数,每个数$m$个属性,一个数比另一个数大,当且仅当这个数的所有属性都大于另一个数。

这就是一个$m$维偏序。

分析


树状数组解决二维偏序问题

二维偏序的详细分析

 

未待完续~~

原文地址:https://www.cnblogs.com/wizarderror/p/11451204.html