CF543E Listening to Music

请注意，本题的内存限制不同于标准设置。 你非常喜欢听音乐。在接下来的 $s$ 天里，每天你会从播放列表中听 $m$ 首歌，播放列表总共有 $n$ 首歌。我们将播放列表中的歌曲编号为 $1$ 到 $n$。第 $i$ 首歌的质量是 $a_{i}$。 在第 $i$ 天，你会选择一个整数 $v$（$l_{i} \le v \le r_{i}$），然后连续听编号为 $v, v+1, \ldots, v+m-1$ 的 $m$ 首歌。在第 $i$ 天，如果你听到一首歌的质量小于 $q_i$，你的不满值会增加 $1$。 请你计算在每一天中，你能获得的最小不满值。

第一行包含两个正整数 $n, m$（$1 \le m \le n \le 2 \cdot 10^{5}$）。 第二行包含 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n}$（$0 \le a_i < 2^{30}$），表示播放列表中每首歌的质量。 接下来一行包含一个整数 $s$（$1 \le s \le 2 \cdot 10^{5}$），表示你要考虑的天数。 接下来的 $s$ 行，每行包含三个整数 $l_i, r_i, x_i$（$1 \le l_i \le r_i \le n-m+1$；$0 \le x_i < 2^{30}$），描述第 $i$ 天的参数。$q_i$ 的计算方式如下： $$ q_i = x_i \oplus ans_{i-1} $$ 其中 $ans_{i}$ 是第 $i$ 天的问题答案，$ans_{0}=0$。

输出恰好 $s$ 个整数 $ans_1, ans_2, \ldots, ans_s$，其中 $ans_i$ 表示你在第 $i$ 天能获得的最小不满值。

由 ChatGPT 5 翻译