其实就是 ABC465F。
Difficulty：4.6 / Medium-
Tag：容斥原理
题意解析：给定你 nnn 个 kkk 元组 AAA，每个有一个权值，qqq 次询问，每次询问给出两个 kkk 元组 x,yx,yx,y，问你满足对于所有 1≤j≤k1\le j\le k1≤j≤k 都满足 xj≤Ai,j≤yjx_j\le A_{i,j}\le y_jxj ≤Ai,j ≤yj 的 AiA_iAi 的权值之和。
k=6,n,q≤3×105,0≤Ai,j≤9k=6,n,q\le 3\times 10^5,0\le A_{i,j}\le 9k=6,n,q≤3×105,0≤Ai,j ≤9。
显然，这是一个 666 维偏序问题。常规解法有 O(nlog5n)O(n\log^5 n)O(nlog5n) 的 CDQ 套扫描线树状数组，O(n116)O(n^{\frac{11}{6}})O(n611 ) 的 K-D Tree 和 O(nqkw)O(\frac{nqk}{w})O(wnqk ) 的 bitset（存疑）。显然都很难通过。
注意到这题值域非常小。所以考虑复杂度基于值域的解法。
首先考虑不算 xxx。
我们可以预处理出每种可能的 yyy，求出如果只考虑 Ai,j≤yjA_{i,j}\le y_jAi,j ≤yj 的限制权值之和。查询时查表即可。
这一部分可以枚举子集，将某些 yjy_jyj 减一，然后容斥起来。
比如说计算 y={3,5,1,2,3,5}y=\{3,5,1,2,3,5\}y={3,5,1,2,3,5}，就可以通过 y={3,5,1,2,3,4},{3,5,1,2,2,5},{3,5,1,2,2,4},...,{2,4,0,1,2,4}y=\{3,5,1,2,3,4\},\{3,5,1,2,2,5\},\{3,5,1,2,2,4\},...,\{2,4,0,1,2,4\}y={3,5,1,2,3,4},{3,5,1,2,2,5},{3,5,1,2,2,4},...,{2,4,0,1,2,4} 一共 2k2^k2k 种子集容斥起来计算。有些 yyy 包含 000，不需要把含 000
的那几位减一。
然后考虑算 xxx。
如果有 xj>yjx_j\gt y_jxj >yj ，显然答案为 000。考虑所有 xj≤yjx_j\le y_jxj ≤yj 的情况。
显然，依旧可以容斥。我们可以枚举 kkk 元组 z={(x1−1或y1),(x2−1或y2),(x3−1或y3),(x4−1或y4),(x5−1或y5),(x6−1或y6)}z=\{(x_1-1或y_1),(x_2-1或y_2),(x_3-1或y_3),(x_4-1或y_4),(x_5-1或y_5),(x_6-1或y_6)\}z={(x1 −1或y1 ),(x2 −1或y2 ),(x3 −1或y3 ),(x4 −1或y4 ),(x5 −1或y5 ),(x6 −1或y6 )} 共 2k2^k2k 种，分别求出 Ai,j≤zjA_i,j\le z_jAi ,j≤zj
的权值之和，然后容斥计算。显然可以查上面的表。
朴素枚举每一位可以做到 O(n+k20k+qk2k)O(n+k20^k+qk2^k)O(n+k20k+qk2k)，精细化实现可以省掉一个 kkk。具体见代码。ATCoder 官方使用了一种更巧妙的实现方法，做到了 O(n+k10k)O(n+k10^k)O(n+k10k) 预处理。我不会，所以就不写了。
时间复杂度：O(n+20k+q2k)O(n+20^k+q2^k)O(n+20k+q2k)。
