P12726 [KOI 2021 Round 2] 连续的 1

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

使用正整数 $N$ 构造的字符串 $S_N$ 定义如下。这里的 $\lfloor N/2 \rfloor$ 表示 $N$ 除以 2 的向下取整值。 1. 当 $N = 1$ 时：$S_N = 1$（即由一个字符 `'1'` 组成的字符串）。 2. 当 $N \geq 2$ 且 $N$ 是偶数时：$S_N = S_{\lfloor N/2 \rfloor} 0 S_{\lfloor N/2 \rfloor}$（即用一个字符 `'0'` 夹在两个 $S_{\lfloor N/2 \rfloor}$ 之间）。 3. 当 $N \geq 2$ 且 $N$ 是奇数时：$S_N = S_{\lfloor N/2 \rfloor} 1 S_{\lfloor N/2 \rfloor}$（即用一个字符 `'1'` 夹在两个 $S_{\lfloor N/2 \rfloor}$ 之间）。 根据上述定义，我们可以如下计算 $S_{13}$： - 由于 $N = 13$ 是奇数，适用第 3 条规则，因此 $S_{13} = S_6 1 S_6$。 - 又由于 $S_6$ 是偶数，适用第 2 条规则，因此 $S_6 = S_3 0 S_3$，所以 $S_{13} = S_3 0 S_3 1 S_3 0 S_3$。 - 而 $S_3$ 是奇数，进一步展开得到 $S_3 = S_1 1 S_1$，而 $S_1 = 1$，所以 $S_3 = 1 1 1$。 因此，$S_{13} = 111011111110111$。 给定正整数 $N$，你需要编写程序处理 $Q$ 个查询。 第 $q$ 个查询（$1 \leq q \leq Q$）给出三个整数 $(i_q, j_q, k_q)$，要求回答：在 $S_N[i_q..j_q]$ 区间中，最多包含 $k_q$ 个 `'0'` 的最长子字符串的长度是多少？ 例如： - 查询 $(1, 15, 0)$ 询问的是整个 $S_{13}$ 中只包含 `'1'` 的最长子串，其长度为 7。 - 查询 $(2, 14, 2)$ 涉及子串 $S_{13}[2..14] = 1101111111011$，其中恰好有两个 `'0'`，因此整个子串就是答案，长度为 13。 部分字符串的定义如下： - 给定一个长度为 $l$ 的字符串 $s$ 和两个满足 $1 \leq i \leq j \leq l$ 的整数 $i$ 和 $j$，$s[i..j]$ 表示从第 $i$ 个字符开始到第 $j$ 个字符为止的所有字符所组成的字符串。 - 例如：若 $s = 0100101$，则 $s[3..5] = 001$，$s[4..7] = 0101$，而 $1010$ 不是其子串。

第一行包含两个整数 $N$ 和 $Q$，用一个空格隔开。 接下来的 $Q$ 行，每行三个整数 $i_q$、$j_q$、$k_q$，表示第 $q$ 个查询。

对每个查询，输出一行，仅包含一个整数，即最长子字符串的长度。

**约束条件** - $1 \leq N \leq 10^{18}$ - $1 \leq Q \leq 10\,000$ - 所有查询中 $k_q$ 的总和不超过 $10\,000$，即 $\sum_{q=1}^{Q} k_q \leq 10\,000$ - 对所有 $q$ 满足 $1 \leq i_q \leq j_q \leq |S_N|$（其中 $|S_N|$ 是字符串 $S_N$ 的长度） **子任务** 1. （5 分）$N = 2^t$，其中 $t$ 为非负整数，即 $N$ 是 $1, 2, 4, 8, \ldots$ 等 2 的幂 2. （11 分）$N \leq 1\,000$ 3. （17 分）所有查询中子串长度之和不超过 $100\,000$，即 $\sum_{q=1}^{Q}(j_q - i_q + 1) \leq 100\,000$ 4. （25 分）所有查询中 $k_q = 0$ 5. （42 分）无额外约束条件