题目描述
现有由 $n$ 块小积木拼成的一个长条积木，从左到右的小积木编号依次为 $1..n$，其中第 $i$ 块小积木的颜色为 $c_i$。
小爱现在有 $q$ 个问题，第$i$个问题会包含两个参数 $l_i$,$r_i$，请你帮忙回答，此时可以对所有积木重新染色，在保证若原状态下两块积木颜色相同、染色后两块积木颜色仍保持相同；原状态下两块积木颜色不同、染色后两块积木颜色仍保持不同的情况下，如何染色才能使得染色后，第$l_i$
到$r_i$块积木的颜色编号之和最小？
输入格式
输入第一行，两个正整数 $n$, $q$
第二行，$n$个正整数 $c_1$,$c_2$,$...$,$c_n$,$c$表示积木初始状态下颜色，接下来 $q$ 行，每行两个正整数 $l_i$,$r_i$ 。
输出格式
输出共 $q$ 行，第 $i$ 行表示第 $i$ 个问题的答案。
数据范围
对于 $30\%$的数据，$1 \leq n \leq 100$
对于 $60\%$的数据，$1 \leq n \leq 10^3$
对于 $100\%$的数据，$1 \leq n \leq 10^5$,$1 \leq q \leq 10^5$,$1 \leq l_i\leq r_i \leq n$,$1 \leq c_i \leq 10^9$
题解
第一步：
理解题意，染色可以任意调整，但要保证前提条件。实际上就是颜色出现次数最多的图上编号为1的颜色，颜色出现次数次多的图上编号为2的颜色，以此类推，把这些数值求和即可。
第二步：
思考算法，根据数据范围和离线的特性，很容易联想到莫队算法。莫队算法转移要保证$O(1)$，整体复杂度$O(q\sqrt{n})$。所以就思考如何才能$O(1)$去转移。
第三步：
进一步思考，我们可以维护一个有序的数组，数组中存储以颜色出现次数，从大到小排序。
例如：
$7,7,6,6,6,6,3,1$ 代表有两种颜色出现7次，四种颜色出现6次，一种颜色出现3次，一种颜色出现1次。
7,7,6,6,6,6,3,1
中间红6代表那种颜色增加了一次，那数组就先变为:
7,7,6,6,6,6,3,1
再变为:
7,7,7,6,6,6,3,1
如果颜色减少了一次，那就和末尾相同元素交换。我们仅靠交换两个元素的位置同时辅助更新一些信息就可以动态维护顺序的不变性。由于变动的只有两个元素，我们也可以很轻易的更新答案。
最后的思考：
我该如何快速的找到与我相同的出现次数的首末位置呢？用倍增或者二分都是可以的，但时间复杂度多了$log$,虽然也很快不好说是不是很稳定的通过题目。仔细思考，我发现这个首末位置我们仍可以保存下来，再交换或者没有交换的时候，我们同时更新受影响的首末位置，这块处理比较考虑细节，不过$O(1)$可以完成。
月赛时提交的是带二分程序，虽然能过初测但怕还是不稳定。补交$O(q\sqrt{n})$ 程序确实快了不少。代码太丑了，不贴了。
补充一点数据结构：
int head[N],tail[N];
//head[i] 出现i次的颜色在有序数列中首次位置。
//tail[i] 出现i次的颜色在有序数列中末次位置。
pari<int,int> rnk[N];//有序数列，以颜色出现次数排序
//first: 颜色出现的次数。
//second: 离散化后颜色的编号。
idx[N];//颜色标号为索引存储rnk数列位置。
评论 (0)