T1

100%

根据题意计算周长，然后判断每条边的长度是否小于周长的一半即可。

时间复杂度 $O(n)$ 。

T2

100%

由于购买一个升级包后必须丢弃两个，贪心考虑肯定每次购买最大的一个，丢弃最小的两个

将所有升级包从小到大排序，看最大的能选多少个即可。

时间复杂度 $O(n \log n)$ 。

T3

100%

首先定义差异数组：

$$d[i]= \begin{cases} 1 & \text{如果 }s[i]\neq t[i] \\ 0 & \text{如果 }s[i]=t[i] & & \end{cases}$$

原问题等价于：在 $d$ 上每次选择一个区间并翻转其中的所有值，求将 $d$ 变为全 0 的最少操作次数。

我们发现，如果翻转区间内包含 0，那么 0 会变成 1，这意味着创造了新的差异段，不会让总操作数更优。因此，每次操作恰好翻转一段连续的 1 总是最优的。

因此最少操作次数等于 $d$ 中连续 1 的段数，遍历一遍，统计 $s[i] \neq t[i]$ 且 $s[i-1] = t[i-1]$ 的个数即可。

时间复杂度 $O(n)$ 。

T4

100%

首先需要判断所有 $d_i$ 的和是否等于 $n-1$， 如果不等于，$m$ 次操作之后区间不会收缩成单点。故方案数均为 $0$。

然后假设最终需要收缩为单点 $[k,k]$ 那么左端点需要移动的长度为 $k-1$ ，接下来的问题为从 $m$ 个数中选出若干个数，他们的和等于 $k-1$ 的方案数，显然是一个0/1背包的模型，对于每个数只需要考虑选或不选进行转移。

令 $dp[i][j]$ 表示前 $i$ 个数，当前选了的和为 $j$ 的方案数，转移为：

$$dp[i][j]=dp[i-1][j]+dp[i-1][j-d_i]$$

初始状态为 $dp[0][0]=1$

时间复杂度 $O(n m)$，空间复杂度 $O(n m)$ （ $dp$ 第一维可以优化）。

T5

100%

首先将原串分成若干段连续的 1 的串，对于一段连续的1的字符串，使用最少的操作次数将其修改为不存在相邻的 1 的字符串，并且要保证字典序最小，修改方式是固定的：对于长度偶数的字符串，翻转其奇数位置的 1,对于长度奇数的字符串，翻转其偶数位置的 1。

$$1111 \to 0101$$ $$11111 \to 10101$$

保证了条件满足后，若有多余的操作次数，一定优先将位置最靠前的 1 改为 0 才能使字典序最小，因此可以计算出每个多余的操作应该翻转的位置。

预处理出能得到满足条件的字符串所需要的最小操作次数，以及后续多余的每个操作应该操作的位置；对于每个查询，先计算出第 $k$ 次操作所修改的位置 $pos$，那么 $pos$ 之后的所有 1 都是保留的，因此对 $[pos+1,n]$ 和 $[l,r]$ 两个区间求交集，通过前缀和求交集的 1 的个数即可。

时间复杂度 $O(n + Q)$。

T6

100%

首先最终的错列串只有两种可能的形态：010101... 或 101010...，可以通过区间长度以及 01 的个数来判断。

可以发现，通过交换相邻变成目标序列的最小操作次数，等于将原序列中的所有 0 (或 1)的位置，与目标序列中的所有 0(或 1)的位置，按顺序对应的距离之和。 更形式化地，设原串中第 $i$ 个 0 的下标为 $p_i$，目标串为 010101...，目标串中第 $i$ 个 0 的下标为 $2i-1$，则最小操作次数为：

$$\sum_{i=1}^{c_0}|p_i-(2i-1)|$$

例如原序列 000111 到目标序列 010101 的操作次数为 $|1-1|+|2-3|+|3-5|=3$。

对于区间查询 $[l,r]$，$[l,r]$ 中的 0 分别是原数组中的第 $L$ 到第 $R$ 个，设原串中第 $i$ 个 0 的下标为 $p_i$，假设目标串为 010101... 最终的操作次数为:

$$\sum_{i=L}^R | p[i] - (l+ 2(i-L)) |$$

对于这样的式子，我们可以将所有带 $i$ 的项看作整体，定义：

$$w[i]=p[i]-2i$$

原式即可化为：

$$\sum_{i=L}^R | w[i] - K |$$

其中 $K=l-2L$ 在单次查询下为常数。

接下来我们只需要求所有 $w[i]$ 与一个常数 $K$ 的差的绝对值之和。

由于带有绝对值，因此我们需要快速求出区间 $[L,R]$ 中，所有 $\leq K$ 的元素个数 $cnt$ 以及他们的总和 $sum$，即可分成两个部分去绝对值计算答案：

$$\sum|x-K|=K\cdot cnt_{\leq K}-sum_{\leq K}\mathrm{~+~}(sum_{\mathrm{total}}-sum_{\leq K})-K\cdot(cnt_{\mathrm{total}}-cnt_{\leq K}) $$

求 $cnt$ 和 $sum$ 的过程是一个二维数点问题：

首先将序列第 $j$ 个元素 $(j,w[j])$ 看作点，对于询问 $[L,R]$，通过差分得到（求和同理），即可转化为前缀查询：

$$cnt_{[L,R],\leq K}=cnt_{[1,R],\leq K}-cnt_{[1,L-1],\leq K} $$

然后将所有询问离线，将所有点 $(j,w[j])$ 按 $w[j]$ 升序排序，将所有前缀查询（$(R,K),(L-1,K)$）按 $K$ 升序排序，用两个树状数组分别维护个数和总和，下标为 $j$，依次处理排序后的询问，每当当前询问的 $K$ 大于大于等于当前点的 $w[j]$ 时,就将该点插入树状数组，然后对当前询问查询前缀和得到 $cnt_{[1,idx],\leq K}$ 和对应的 $sum$。最后利用公式：

$$\sum|x-K|=K\cdot cnt_{\leq K}-sum_{\leq K}\mathrm{~+~}(sum_{\mathrm{total}}-sum_{\leq K})-K\cdot(cnt_{\mathrm{total}}-cnt_{\leq K}) $$

即可得到答案。

时间复杂度为 $O( (n+Q) \log n )$ 。