A题挣扎好久不会做。
B题给出n个数的序列，然后每次询问$min(abs(a[i]-k))i∈[l,r]$ $n<=20W$
我们发现是个傻逼数据结构题。
先建立主席树，把问题转化为要查询一段区间$[l,r]$内，权值属于某个$[a,b]$的最大的数或者最小的数。
这个单次询问是$O(logn)$的。
不放认为现在要查询最大的数。
我们可以这样搞，首先$[a,b]$覆盖到线段树的节点上是$O(logn)$个完整的区间。我们优先遍历靠右的节点。
每个完整的节点是否有我们需要的数只要判断$s[]$是否$=0$.即可。一旦有一个节点满足$s[]！=0$.那我们就可以继续
$O(logn)$遍历下去找到我们的$ans$。否则$O(1)$判断走其他子树。
出题人给的解法是离线的：
求m$in(|Ai - K|)$可以分解为求$Ai -K (Ai ≥ K)$和$K - Ai(Ai < K)$的最小值。
首先考虑第一种情况，将所有$K$和$Ai$在一起按从大到小排序。
维护一个范围$[1, N]$的线段树，依次把$Ai$插入线段树的第$i$个节点；对每个$K$查询线段树中$[L, R]$内最小的$Ai$。第二种情况也类似。
玛雅怎么又是从小到大加入
C题给出n个点，每个点有一种颜色$a[i]∈[1,k]$。然后现在想让颜色相同的全部在一块。每次可以交换相邻的两个数。
问最少交换次数。$n<=100000 k<=16$
这个题其实并不难。
很容易想到$dp[i][j]$表示把$j$集合里的颜色全部放到前$i$个数里面的最小花费。
但这是很傻逼的。因为一个集合只可能被固定的i搞到，就是这个集合内的所有颜色的个数和。
因此这启发我们设计状态$dp[i]$表示把i集合的颜色全部放到最左端的最小花费。
然后我们可以枚举最后一个放的颜色j从而转移。$$dp[i]=min(dp[i-\{j\}]+addcost(j,i-\{j\})$$
那么新加入颜色$j$之后这个$cost$怎么算呢？
实际上如果我们知道了前面的颜色集合，那么$j$颜色在他们移动完了之后的位置一定是确定的。
但我们如果去找$j$颜色所在的所有位置，然后一个个移到该到的位置，感觉复杂度不靠谱。
这样是$O(n*2^{k-1})$的。
实际上，如果我们确定了一个颜色顺序。
那么我们只要把每个颜色的权值设为它的顺序，然后套用经典的树状数组算法。
就可以知道把这个序列变成不降序列且只能交换相邻的两个数的最小交换次数。
就是这个序列逆序对啦
那么这道题我们也可以用这个思想。
当前不在集合中的我们只要把它的权值认为是$inf$即可。
那么当我们在序列尾部加入一个颜色$j$的时候，我们只要加入仍为$inf$的颜色且在原序列中在j颜色的前面的机器人的数目。
这个可以预处理出来。令$a[i][j]$表示每个$i$颜色的机器人前面的$j$颜色的机器人的个数和。
那么我们的状态转移方程就是$$dp[i]=min(dp[i-\{j\}]+\sum_{p∉i}a[j][p])$$
时间复杂度$O(nk+2^kk^2)$
评论 (0)
