P14984 [USACO26JAN1] Lineup Counting Queries P

有一队奶牛，初始时（即时刻 $t = 0$）只有奶牛 $0$ 在位置 $0$（这里，一头奶牛在位置 $k$ 表示它前面有 $k$ 头奶牛）。在时刻 $t$（$t=1,2,3,\dots$），位置 $0$ 的奶牛移动到位置 $\lfloor t/2\rfloor$，位置 $1\dots \lfloor t/2\rfloor$ 上的每头奶牛向前移动一个位置，并且奶牛 $t$ 加入到队列的末尾（位置 $t$）。 回答 $Q$（$1\le Q\le 10^5$）个独立的查询，每个查询形式如下： - 在奶牛 $l_1\dots r_1$ 中，有多少头在时刻 $t$ 刚结束时位于位置 $l_2\dots r_2$ 上？（$0\le l_1\le r_1\le t, 0\le l_2\le r_2 \le t, t\le 10^{18}$）

第一行包含 $Q$，表示查询的数量。 接下来的 $Q$ 行，每行包含五个整数，指定一个查询，格式为 "$l_1$ $r_1$ $l_2$ $r_2$ $t$"。

将每个查询的答案输出在单独一行。

不同时刻的队列排列： ```none t = 0 | 0 t = 1 | 0 1 t = 2 | 1 0 2 t = 3 | 0 1 2 3 t = 4 | 1 2 0 3 4 t = 5 | 2 0 1 3 4 5 t = 6 | 0 1 3 2 4 5 6 t = 7 | 1 3 2 0 4 5 6 7 t = 8 | 3 2 0 4 1 5 6 7 8 t = 9 | 2 0 4 1 3 5 6 7 8 9 ``` 在 $t=9$ 时，从前到后的奶牛依次是 $[2,0,4,1,3,5,6,7,8,9]$。 为了回答第三个查询，位置 $3\dots 5$ 上的奶牛是 $[1,3,5]$，其中只有一头在范围 $4\dots 5$ 内。 --- - 输入 $3$：$Q\le 1000, t\le 100$ - 输入 $4$-$7$：所有查询中 $l_1 = r_1$ - 输入 $8$-$14$：所有查询中 $r_1 \leq 2 \cdot l_1$ - 输入 $15$-$21$：无额外约束。 翻译由 DeepSeek V3 完成