4042. 有效 K 个不同元素子数组 II 🔒

题目描述

给定一个长度为 n 的整数数组 nums 和一个整数 k。

同时给定整数 l0 和 r0，它们定义了第一个查询，以及一个整数 q，表示需要处理的查询总数。

如果一个 子数组 nums[l_i..r_i] 满足以下条件，则称其为有效子数组：

对于查询 0，令 l₀ = l0，r₀ = r0。

令 ans_i 表示第 i 个查询的结果，其中：

对于每个 i > 0，按照以下方式生成下一个查询：

返回一个布尔数组 ans，其中 ans[i] 在 ans_i = 1 时为 true，否则为 false。

示例 1：

输入： nums = [1,2,2,1], k = 2, l0 = 1, r0 = 2, q = 2

输出： [false,true]

解释：

`i`	`[l_i, r_i]`	子数组	不同数字	出现次数	有效性判断	`ans[i]`	`[l_i+1, r_i+1]`
0	[1, 2]	[2, 2]	{2} → 1	{2:2}	`false`：该子数组包含的不同数字少于 `k` 个。	`ans₀ = 0`	`g₀ = 2 - 1 = 1 l₁ = (1 XOR 1) % 4 = 0 r₁ = (2 XOR 1) % 4 = 3`
1	[0, 3]	[1, 2, 2, 1]	{1,2} → 2	{1:2,2:2}	`true`：该子数组恰好包含 `k` 个不同数字，并且每个数字出现的次数都是偶数。	`ans₁ = 1`	-

因此，ans = [false, true]。

示例 2：

输入： nums = [1,2,3,3,4], k = 1, l0 = 2, r0 = 3, q = 2

输出： [true,false]

解释：

`i`	`[l_i, r_i]`	子数组	不同数字	出现次数	有效性判断	`ans[i]`	`[l_i+1, r_i+1]`
0	[2, 3]	[3, 3]	{3} → 1	{3:2}	`true`：该子数组恰好包含 `k` 个不同数字，并且每个数字出现的次数都是偶数。	`ans₀ = 1`	`g₀ = 2 + 3 = 5 l₁ = (2 XOR 5) % 5 = 7 % 5 = 2 r₁ = (3 XOR 5) % 5 = 6 % 5 = 1` 由于 `l₁ > r₁`，交换二者，得到 `[l₁, r₁] = [1, 2]`。
1	[1, 2]	[2, 3]	{2,3} → 2	{2:1,3:1}	`false`：该子数组包含 2 个不同数字，而不是恰好 `k = 1` 个。	`ans₁ = 0`	-

因此，ans = [true, false]。

提示：

Python3JavaC++Go