巧妙的数位 d p dp dp
根据回文那套理论我们从两边往中间 d p dp dp就好了，要求字典序第 k k k小就从高到低位确定即可
暴力状压+状态剪枝
显然找规律啊
观察到这是一个分形图
那么显然我们可以递归处理每个询问，把它分裂成四个小的矩形区域进行求解
对于整块的询问因为每行每列都是一个排列所以也很容易求得
因为横纵坐标都会分裂成 log n \log n logn个区间所以单次询问复杂度 O ( log 2 n ) O(\log^2 n) O(log2n)
对不起复杂度是伪的
根据分形图的定义我们知道 a [ i ] [ j ] = ( i − 1 ) ⊕ ( j − 1 ) + 1 a[i][j]=(i-1)\oplus (j-1)+1 a[i][j]=(i−1)⊕(j−1)+1
将查询的坐标都减 1 1 1，答案是 ∑ i = l 1 r 1 ∑ j = l 2 r 2 ( i ⊕ j + 1 ) [ i ⊕ j ≤ k − 1 ] \sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}(i\oplus j+1)[i\oplus j\le k-1] ∑i=l1r1∑j=l2r2(i⊕j+1)[i⊕j≤k−1]
化成前缀和的形式然后数位 d p dp dp即可。
不会