代码如诗

划分数组得到最小的值之和

给你两个数组 nums 和 andValues，长度分别为 n 和 m。

数组的 值 等于该数组的 最后一个 元素。

你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组 `[li,

ri]，子数组元素的按位AND运算结果等于andValues[i]，换句话说，对所有的1 <= i <= m，nums[li] &

nums[li + 1] & ... & nums[ri] == andValues[i]，其中&表示按位AND`运算符。

返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 -1 。

示例 1：

输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]

输出： 12

解释：

唯一可能的划分方法为：

1. [1,4] 因为 1 & 4 == 0

2. [3] 因为单元素子数组的按位 AND 结果就是该元素本身

3. [3] 因为单元素子数组的按位 AND 结果就是该元素本身

4. [2] 因为单元素子数组的按位 AND 结果就是该元素本身

这些子数组的值之和为 4 + 3 + 3 + 2 = 12

示例 2：

输入： nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

输出： 17

解释：

划分 nums 的三种方式为：

1. [[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 + 7 + 5 = 17

2. [[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

3. [[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

子数组值之和的最小可能值为 17

示例 3：

输入： nums = [1,2,3,4], andValues = [2]

输出： -1

解释：

整个数组 nums 的按位 AND 结果为 0。由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2，因此返回

-1。

提示：

• 1 <= n == nums.length <= 104

• 1 <= m == andValues.length <= min(n, 10)

• 1 <= nums[i] < 105

• 0 <= andValues[j] < 105

不包含相邻元素的子序列的最大和

给你一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi]。

对于每个查询 i，首先将 nums[posi] 设置为 xi，然后计算查询 i 的答案，该答案为 nums 中 不包含相邻元素

的子序列的 最大 和。

返回所有查询的答案之和。

由于最终答案可能非常大，返回其对 109 + 7 取余 的结果。

子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。

示例 1：

输入： nums = [3,5,9], queries = [[1,-2],[0,-3]]

输出： 21

解释：

执行第 1 个查询后，nums = [3,-2,9]，不包含相邻元素的子序列的最大和为 3 + 9 = 12。

执行第 2 个查询后，nums = [-3,-2,9]，不包含相邻元素的子序列的最大和为 9 。

示例 2：

输入： nums = [0,-1], queries = [[0,-5]]

输出： 0

解释：

执行第 1 个查询后，nums = [-5,-1]，不包含相邻元素的子序列的最大和为 0（选择空子序列）。

提示：

• 1 <= nums.length <= 5 * 104

• -105 <= nums[i] <= 105

• 1 <= queries.length <= 5 * 104

• queries[i] == [posi, xi]

• 0 <= posi <= nums.length - 1

• -105 <= xi <= 105

物块放置查询

有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。

给你一个二维数组 queries ，它包含两种操作：

1. 操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。

2. 操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要 完全 放置在范围 [0, x] 内。如果物块与任何障碍物有重合，那么这个物块 不能 被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并 不是 真的放置这个物块。每个查询都是相互独立的。

请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为

true ，否则为 false 。

示例 1：

输入： queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]

输出：[false,true,true]

解释：

查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。

示例 2：

输入： queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]

输出：[true,true,false]

解释：

• 查询 0 在 x = 7 处放置一个障碍物。在 x = 7 之前任何大小不超过 7 的物块都可以被放置。

• 查询 2 在 x = 2 处放置一个障碍物。现在，在 x = 7 之前任何大小不超过 5 的物块可以被放置，x = 2 之前任何大小不超过 2 的物块可以被放置。

提示：

• 1 <= queries.length <= 15 * 104

• 2 <= queries[i].length <= 3

• 1 <= queries[i][0] <= 2

• 1 <= x, sz <= min(5 * 104, 3 * queries.length)

• 输入保证操作 1 中，x 处不会有障碍物。

• 输入保证至少有一个操作类型 2 。

A. Phone Desktop

B. Symmetric Encoding

C. Beautiful Triple Pairs

D. Ingenuity-2

E. Money Buys Happiness

F. Cutting Game

G. Money Buys Less Happiness Now

给出一个长度为n的浮点数数组a。数组每个值在0到1之间。

现在你要n个人出题。

第i个人出题成功的概率为a[i]

如果可以从n个人中选一些人出题，恰好只有一个人出题的最大概率是多少？

小 P 有 $n$ 场考试要考，它们的开始时间是 $a_1\sim a_n$（保证 $a$ 按升序排列），所有的考试都会在 $d$ 之前结束。

对于时间相邻的两场考试 $a_{i-1},a_{i}$，定义它们的距离为 $a_{i}-a_{i-1}-1$，而 $a_1$ 与 $a_{0}$ 的距离定义为 $a_1$ 与 $0$ 的距离。

定义对于这个数组 $a$ 的 $\mu$ 值为所有 $a_{i-1}$ 与 $a_{i}$ 之间距离的最小值。

你可以改变某一个 $a_i$ 的值（但不能 $>d$），最大化修改后 $a$ 的 $\mu$ 的值，输出最大的 $\mu$ 值。

翻译提供者：@DaiRuiChen007

给定整数 $n$ 和一个 $1\sim n$ 的排列 $p$。

你可以对排列 $p$ 进行下列操作任意次：

• 选择整数 $i,j(1\leq i<j\leq n)$，然后交换 $p_i,p_j$ 的值。

你需要求出至少需要进行上述操作多少次才能使 $p$ 恰有一个逆序对。

每个测试点包含 $t$ 组数据。

输入格式

第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数，接下来对于每组数据：

第一行输入一个整数 $n(2\leq n,\sum n\leq2\times10^5)$。

接下来输入一行 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$，保证 $p$ 是一个 $1\sim n$ 的排列。

输出格式

对于每组数据：

输出一行一个整数表示使 $p$ 恰有一个逆序对所需的最小操作次数。

可以证明一定存在操作方案使得 $p$ 恰有一个逆序对。