#P15642. [Bulgarian2023秋季赛]coloring涂色

[Bulgarian2023秋季赛]coloring涂色

题目描述

给定一个长度为 NN 的整数序列

a1,a2,…,aNa_1,a_2,\ldots,a_N

以及 QQ 个询问。第 ii 个询问由两个整数 xi,yix_i,y_i 描述。

对于一次询问,先将序列中所有值等于 xix_i 或 yiy_i 的位置染色。设染色位置为

p1,p2,…,pk.p_1,p_2,\ldots,p_k.

我们希望通过交换相邻两个数,使得下式尽可能小:

∑i=1k∑j=1k∣pi−pj∣.\sum_{i=1}^{k}\sum_{j=1}^{k}|p_i-p_j|.

每交换一次相邻两个数,需要花费 11 元。

对于每个询问,请输出为了使上述双重求和达到最小值所需的最小花费。

输入格式

第一行包含两个正整数 N,QN,Q,分别表示序列长度和询问数。

第二行包含 NN 个正整数 a1,a2,…,aNa_1,a_2,\ldots,a_N。

接下来 QQ 行,每行包含两个整数 xi,yix_i,y_i,表示一次询问。

输出格式

输出 QQ 行,第 ii 行表示第 ii 个询问的答案。

数据范围

  • 2≤N≤1062\le N\le 10^6;
  • 1≤Q≤1061\le Q\le 10^6;
  • 1≤ai,xi,yi≤N1\le a_i,x_i,y_i\le N;
  • 保证 xix_i 和 yiy_i 都在原序列中出现;
  • 保证 xi≠yix_i\ne y_i;
  • 保证原序列中至少有两种不同的值。

子任务

子任务 依赖子任务 分值 N,QN,Q 其他限制
1 无 0 无 样例测试
2 1 15 ≤15\le 15 无
3 1-2 13 ≤500\le 500
4 1-3 ≤10000\le 10000
5 1-4 29 ≤200000\le 200000
6 1-5 30 ≤106\le 10^6

一个子任务的分数只有在该子任务及其依赖子任务全部通过时才能获得。

样例 1

输入

5 4
1 2 3 1 4
1 2
1 3
1 4
2 4

输出

1
1
2
2

样例 2

输入

10 6
5 2 1 3 1 3 3 2 1 2
1 2
2 3
3 1
1 5
5 2
3 5

输出

8
4
1
6
11
4