剪贴板连接

T398162 [ICPC2021 Nanjing R] Klee in Solitary Confinement

翻译（by xiaoyun233）

[ICPC2021 南京 R] 禁闭中的可莉

题目背景

1秒，256MB限制

题目描述

自从旅行者来了以后，蒙德城的人们突然对计算机编程、算法产生了极大兴趣,其中包括西风骑士团的火花骑士——可莉。

由于再次被琴关了禁闭，可莉决定去费一些时间研究著名的莫队算法，在没有改进的情况下，可以以 $O (n^{1.5})$ 的时间复杂度解决一些范围查询问题。

为了检查可莉是否真的掌握了该算法（或者其实为了是检查她是否在偷偷制造别的炸弹），琴给了她一个问题，包括一个长度为 $n$ 的整数序列 $a_1$ , $a_2$ ,···, $a_n$ ，以及一些要求她在连续子序列 $a_{l_i}$ , $a_{l_i+1}$ ,···, $a_{r_i}$ 中找到众数的区间 $[l_i,r_i]$ ——众数指的是序列中最普遍的数（也就是出现最多的数字）。

在莫队算法的帮助下，可莉不费吹灰之力就解决了这个问题。但是，她又想到了别的问题。给定一个长度为 $n$ 的整数序列 $a_1$ , $a_2$ ,···, $a_n$ 以及一个整数 $k$ ，你可以执行最多一次以下操作：选择两个满足 $1 \le l \le r \le n$ 的整数 $l$ 和 $r$ ，然后给 $l\le i \le r$ 范围内的每个 $a_i$ 都加上 $k$ 。注意，你也可以不执行操作。计算你以最佳方案执行(或不执行）操作后整个序列众数的最大出现次数。

输入格式

每个测试文件中只有一个测试用例。

输入的第一行包含两个整数 $n$ 和 $k$ ( $1 \le n \le 10^6$ ， $-10^6\le k \le 10^6$ ) ，表示整数序列的长度和操作要相加的数。

输入的第二行包含 $n$ 个整数 $a_1$ , $a_2$ ,···, $a_n$ ( $-10^6\le a_i \le 10^6$ ) ，表示最初的序列。

输出格式

输出一行，包含一个整数，表示在执行（或不执行）操作之后整个序列的众数的最大出现次数。

输入输出样例

见原题

说明/提示

在第一个测试样例中，选择 $l=1$ 以及 $r=2$ 。然后我们将会得到序列 { $4,4,4,4,4$ }。很明显，众数是出现了 $5$ 次的 $4$ 。

在第二个测试样例中，选择 $l=4$ 以及 $r=6$ 。然后我们将会得到序列 { $3,2,3,3,3,3,3$ }。众数是出现了 $6$ 次的 $3$ 。

在第三个测试样例中，选择不去执行操作。众数是同样出现了 $3$ 次的 $1$ 和 $-2$ 。

2024/1/11 19:04

原帖子（证明是我发的）