感觉都不是很好做

难不成是贪心专场？

T3

考虑线段树上维护某些信息

维护一个数组，表示从左往右或从右往左依次出现的字符为什么

这样子只需要记录30种不同的数即可

因为n只给到 $5\times 10^4$ ，所以很容易想到双log做法

我们把其中一个log换成 k 即可得到 $O(nklogn)$ 的做法

然后就过了？

希望能过

T1

感觉像贪心，但是死活猜不出结论

不妨设数量少的那一边在下方

设 $f_{i,j}$ 表示当前选到第i个下方点，第j个上方点的最小权值

那么有转移

$f_{i,j}=\min_{k<j} f_{i-1,k}+ \mid a_j-a_i \mid$

发现当 $j$ 固定时一切都固定了

但这样是拿不了满分的

算了就这样吧，说不定接下来还有贪心结论

草，看错题了

T2

感觉好像在哪里见过

根据相对运动的观点，一个字母往左移等价于另一个字母往右移

所以最后面一定存在一种方案为安排好左边再向右拓展

两个相同的字符不会交换，因为那样子没有意义

区间dp？

设 $f_{i,j,a,b}$ 表示 $[i,j]$ 这个区间的左右两端字符为 a,b 的最小操作步数

感觉不如T4

T4

考虑枚举区间中最大的数

问题就变成了“有多少个经过某点的区间满足异或起来比一个定值小”

容易想到前缀和，就变成了“有多少个包含某点的两点满足异或起来比一个定值小”

设中点为 $mid$ ，左端点为 $l$ ,右为 $r$

那么答案就是

$\sum_{l \le i <mid}\sum_{mid\le j \le r}[d_i\ xor\ d_j \le a_{mid}]$

主席树？可持久化trie？

容易想到枚举二进制位

完了，考的最炸的一集

这下死光光了

积攒运气吧

哭哭