1001
特殊处理 $n \leq 2$ 的情况。当 $n=k$ 时构造是容易的，当 $k \bmod 2 = 1$ 时可以发现字符串 $ababab\cdots$ 的长度为 $n$ 的前缀总是满足题设条件，故答案为 Yes。对于其他情况，即 $n>k$ 且 $k \bmod 2 = 0$ 的情况，可以将回文串条件可以导出的字符之间相等关系以边的方式画出来，容易证明字符之间总是两两相等，故答案为 No。
1002
首先一个算式肯定是加法和乘法交替的。对于每组连续的加法或者乘法，如果组内的元素是相同的，那么运算的结果也是一样的。假设分成了 $x$ 组加法和 $y$ 组乘法，满足 $|x-y|\leq 1$，那么加法和乘法的分组都是独立的。问题等价于将 $n$ 个有标号的球分到 $m$ 个有标号的集合里面，使得每个集合都是非空的。这个问题可以用第二类斯特灵数简单解决。
所以总的时间复杂度是 $O(m^2+Tm)$ 的。
1003
答案上界显然是 $\sum_{i=1}^n b_i$，即每次操作都让一个点的 $b_i$ 减去 1。考虑在这样的操作基础上将若干次操作合并为一次合法的操作从而减少总操作次数。在树上 dfs，对于每个节点维护其子树尽可能合并后当前节点还有多少个操作能和父亲合并，每个节点计算完所有儿子的子树的答案后贪心地与儿子合并操作。可以发现在可以与儿子合并操作的前提下与儿子合并总是不会比与父亲合并差，所以这样贪心是正确的。记录合并操作次数和即可求得答案。
1004
对于一个确定的序列设 $w_{l,r} = \sum_{i=l}^r \sum_{j=l}^r \mathrm{dist}(a_i,a_j)$，对于一个给定的序列 ${a_1,a_2,\cdots,a_n}$ 容易设计动态规划 $f_{i,j}$ 表示对区间 $[i,j]$ 建立线段树的最小暴跳次数，转移枚举 $\mathrm{mid}$ 的取值，有 $f_{i,j} = \min_{mid=l}^{r-1}f_{l,mid}+f_{mid+1,r}+w_{l,r}$。可以注意到 $w_{l,r}$ 满足四边形不等式，故 $f_{i,j}$ 的转移满足决策单调性，即设 $k_{i,j}$ 表示 $f_{i,j}$ 的转移中取到最小值的 $\mathrm{mid}$ 取值，则 $k_{i,j-1} \leq k_{i,j} \leq k_{i+1,j}$。按照长度依次转移，转移 $f_{i,j}$ 时只枚举区间 $[k_{i,j-1},k_{i+1,j}]$ 中的转移点，复杂度为 $O(n^2)$。对于加入版本的操作，建立出操作树在上面 dfs，每次相当于加入一个元素，新增一列 dp 数组。这一列数组的转移仍然满足决策单调性，使用单调栈求解。需要注意这里不能使用枚举转移点的方式优化，因为其是均摊的，可以被卡到高复杂度。精细实现 $w_{l,r}$ 的求解即可做到 $O(T(m^2+n^2+nr\log n))$ 的时间复杂度。
1005
根据 1002 题的结果，如果直接搜索本质不同的方法，会比较难在时限内通过。
直接搜索就行了。
注意到，假设我们枚举完乘法的顺序，那么我们每个加法操作的贡献只和它们的位置相关，也就是插在哪几个乘法之间，并且是独立的。所以等价于每个加法操作有若干种选择，你要选择数字加起来使得 $\bmod p$ 最小。那么可以用 meet in middle 的方法解决。
然后如果乘法个数大于7的情况，可以直接搜索，会比 meet in middle 快。
1006
首先我们考虑每对点，对答案计算贡献。一对点 $i, j$ 对答案有贡献，当且仅当 $a_i=a_j$ 并且 $i$ 到 $j$ 之间的最大值和最小值都在 $l,r$ 之间。
对于每个数，如果出现了不超过 $B$ 次，那么我们可以把所有这样的点对求出来，一共不会超过 $O(nB)$ 对，区间内的最大值和最小值都可以用 $O(1)$ 的 RMQ 解决，也可以在求出每对相邻点区间内的最大值和最小值之后进行递推，这样一共只需要查 $O(n)$ 次 RMQ，用 $O(\log n)$ 也可以。把这些点对都拿出来之后，容易发现是个二维数点问题，可以通过扫描线解决。注意这里如果用树状数组做，时间复杂度可能会多一个 $\log$。但是修改操作比询问操作多很多，所以可以用修改 $O(1)$，询问 $O(\sqrt{n})$ 的分块做法解决。这部分的时间复杂度是 $O(nB+m\sqrt{n})$ 的。
如果出现次数超过了 $B$ 次，我们考虑每种数字单独解决。假设这个数字出现了 $k$ 次，那么这个数字每次出现的段里的最大值和最小值，会把值域划分成 $O(k)$ 段。如果询问对应的 $l,r$ 在值域中是同一段，那么答案也是一样的。所以我们可以把询问离散化，离散化之后使用莫队算法解决。这里在莫队算法的时候需要维护连续段，我们可以用不删除莫队+链表，就能在 $O(1)$ 的额外代价完成转移。时间复杂度是 $O(k\sqrt{m}+m)$ 的。所以后一半的时间复杂度是 $O(n\sqrt{m}+nm/B)$ 的。
取 $B=\sqrt{m}$，总的时间复杂度是 $O(n\sqrt{m}+m\sqrt{n})$。注意到后半部分的时间复杂度来自于求和的分块，我们可以把求和的结构改成 $t$ 层，每层 $n^{1/t}$。后半部分可以被改进到 $O(mn^{1/t})$。