三维偏序 luogu 3801 金牌导航 CDQ分治-1 题目大意 有n个元素，第i个元素有 a i , b i , c i a_i,b_i,c_i ai​,bi​,ci​三个属性，设 f(i)表示满足 a j ⩽ a i a_j\leqslant a_i aj​⩽ai​且 b j ⩽ b i b_j \leqslant b_i bj​⩽bi​且 c j ⩽ c i c_j \leqsla

题目 分析 首先位运算没有进位，这样可以让它一位一位进行，如题所述，设 x x x表示 a i a_i ai​的第 k k k位，当 l = = r l==r l==r的时候概率为 1 n 2 \frac{1}{n^2} n21​，然后当 x = = 1 x==1 x==1时数学期望为 2 k n 2 \frac{2^k}{n^2} n22k​。 Then，当 l < r l&l