CF117D Not Quick Transformation

给定一个包含 $n$ 个数的数组 $a$。数组元素编号从 $1$ 到 $n$。$even$ 是由 $a$ 中编号为偶数的元素组成的数组（$even_{i}=a_{2i}$，$1 \leq 2i \leq n$），$odd$ 是由 $a$ 中编号为奇数的元素组成的数组（$odd_{i}=a_{2i-1}$，$1 \leq 2i-1 \leq n$）。我们定义数组的变换 $F(a)$ 如下： - 如果 $n > 1$，则 $F(a) = F(odd) + F(even)$，其中“$+$”表示数组的连接（拼接）操作。 - 如果 $n = 1$，则 $F(a) = a$。 设 $a$ 是一个包含 $n$ 个数 $1,2,3,\ldots,n$ 的数组。$b$ 是对数组 $a$ 应用上述变换后的结果（即 $b = F(a)$）。你会得到 $m$ 个询问，每个询问为 $(l, r, u, v)$。你的任务是，对于每个询问，求出所有满足 $l \leq i \leq r$ 且 $u \leq b_i \leq v$ 的 $b_i$ 之和。请将每个询问的结果对 $mod$ 取余后输出。

第一行包含三个整数 $n$、$m$、$mod$（$1 \leq n \leq 10^{18}$，$1 \leq m \leq 10^{5}$，$1 \leq mod \leq 10^{9}$）。接下来 $m$ 行，每行描述一个询问。每个询问由四个整数 $l$、$r$、$u$、$v$ 组成（$1 \leq l \leq r \leq n$，$1 \leq u \leq v \leq 10^{18}$）。

输出 $m$ 行，每行一个整数，表示该询问的答案对 $mod$ 取余后的结果。

我们来看第一个样例。首先构造数组 $b = F(a) = F([1,2,3,4])$。 - 第一步，$F([1,2,3,4]) = F([1,3]) + F([2,4])$。 - 第二步，$F([1,3]) = F([1]) + F([3]) = [1] + [3] = [1,3]$。 - 第三步，$F([2,4]) = F([2]) + F([4]) = [2] + [4] = [2,4]$。 - 第四步，$b = F([1,2,3,4]) = F([1,3]) + F([2,4]) = [1,3] + [2,4] = [1,3,2,4]$。 因此 $b = [1,3,2,4]$。来看第一个询问 $l=2, r=3, u=4, v=5$。数组 $b$ 的第 2 和第 3 个位置都没有在区间 $[4,5]$ 的数，因此和显然为 0。再看第二个询问 $l=2, r=4, u=1, v=3$。第 2 和第 3 个位置有两个数属于区间 $[1,3]$，它们的和为 5。 由 ChatGPT 4.1 翻译