多维偏序

学习笔记

题目背景

现在给你$n$个数,每一个数有$p$种属性,求出偏序数量.
偏序指数对$i,j$对于$\forall k\in{(1,p)} \ a_i<a_j$

p=1

排序就好了.

p=2

第一维排序,第二维树状数组.

p=3

这个就有点难度了.
第一维排序,第二维cdq,第三维树状数组可以很好的解决.

p=4

cdq+cdq+cdq就好了.

p=5

参照上面

p>5

但是,我们分析一下我们的复杂度当$p=k$的时候:
$O(T)=nlog^kn$

如果$k=7,n=100000$,我们大致算一下就是$3.487559486×10^{13}$,你觉得可以过?$Naive$

进阶

如果我们把比他小的看成集合,那么答案就是集合的交的大小.
emmm,C--有一个神奇的东西叫做bitset可以满足我们的要求!
但是你觉得这样子开的下?

bitset<100000>S[k][100010];

那么只要块头预处理中间的暴力算就可以解决了!!!

代码实现