傻卵\(bitset\)题
高位偏序,直接套CDQ分治显然不可行
但是解决高维偏序还有一种常见的 trick:把每一维拆开,用二进制表示出偏序关系,最后全部按位与起来合并。
具体的,对于每一位我们按照\(r\)从小到大排序,固定\(i\),找出所有的\(r_j < r_i\)并在\(bitset\)中标为\(1\)。把所有的\(i\)枚举一遍后的\(bitset\) &AND&起来就是我们想要的答案了
然后只需要套一个显然的\(dp\)即可解决问题
最终复杂度\(O(\frac{n^2m}{w} + nm)\)
标签:偏序,傻卵,原题,复杂度,bitset,CF1826E From: https://www.cnblogs.com/fox-konata/p/17663280.html