#P9574. [APIO2023]序列

    ID: 6183 传统题 1500ms 2048MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-排序与序列处理一维前缀和数据结构懒标记线段树离线与分治离线查询查询排序离散化树状数组CF2900

[APIO2023]序列

题目描述

在 LibreOJ,本题仅保证使用 GNU C++17 编译将得到预期的编译结果,使用其他编译器版本不保证编译结果一定符合预期。

在迷人的 APIO 国,居住一位着年轻智慧的学生 Alice。Alice 对解决能挑战她数学能力的有趣问题有着永不满足的好奇心。一天,她在解决一个神秘的有关长为 NN 的序列(即 A[0],A[1],…,A[N−1]A[0],A[1],\ldots ,A[N - 1])的问题时遇到了困难,她无法抗拒探索答案的诱惑力。

现在,她想要与你分享一些她的发现。不过,为了更好的理解,我们需要给出以下定义:

  • 定义 W(l,r,x)W(l,r,x) 为 ∑i=lrI[A[i]=x]\sum_{i=l}^r \mathbb{I}[A[i]=x],即 xx 在 A[l]…A[r]A[l]\ldots A[r] 中的出现次数。
  • 定义一个非空整数序列 B[0],B[1],…,B[k−1]B[0], B[1],\ldots, B[k - 1] 的中位数集合为 S({B[0],B[1],…,B[k−1]})S(\{B[0],B[1],\ldots ,B[k - 1]\}),然后 Alice 会展示如何分步计算中位数集合:
    • 首先,将序列 B[0],B[1],…,B[k−1]B[0],B[1],\ldots ,B[k-1] 按照升序排序,令排好序的序列为 C[0],C[1],…,C[k−1]C[0],C[1],\ldots ,C[k - 1]。
    • 然后,$S(\{B[0],B[1],\ldots , B[k - 1]\}) = \{C[\lfloor \frac{k-1}{2} \rfloor],C[\lceil \frac{k-1}{2} \rceil]\}$。
    • 为了能更好的理解 SS 的计算,以下为一些例子:
      • S({6,3,5,4,6,2,3})={4}S(\{6,3,5,4,6,2,3\}) = \{4\}
      • S({4,2,3,1})={2,3}S(\{4,2,3,1\}) = \{2,3\}
      • S({5,4,2,4})={4}S(\{5,4,2,4\}) = \{4\}

作为一道具有挑战性的问题,Alice 想对于所有的 (l,r) (0≤l≤r≤N−1)(l,r)\ (0\le l\le r\le N-1) 找到其价值 max⁡x∈S(l,r)W(l,r,x)\max_{x\in S(l,r)}W(l,r,x) 的最大值。其中 S(l,r)S(l,r) 代表 A[l]…A[r]A[l]\ldots A[r] 导出的中位数集合(正如之前提到的 S(A[l],…,A[r])S(A[l],\ldots,A[r]))。虽然 Alice 已经得到了答案,她需要核对答案的正确性,所以她找到了你,希望你能编程解决问题。

实现细节

请在程序开头引入库 sequence.h。

#include "sequence.h"

你需要实现如下的过程:

int sequence(int N, std::vector<int> A);
  • NN:序列 AA 的长度。
  • AA:一个长度为 NN 的数组,即输入中提到的序列 AA。
  • 该函数应返回一个整数,代表所有可行 (l,r)(l,r) 价值的最大值。
  • 这个函数恰好被调用一次。
7
1 2 3 1 2 1 3

3

9
1 1 2 3 4 3 2 1 1

2

14
2 6 2 5 3 4 2 1 4 3 5 6 3 2

3

约束条件

  • 1≤N≤5×1051 \le N \le 5 \times 10^5
  • 1≤A[i]≤N1 \le A[i] \le N

子任务

  1. (1111 分):N≤100N \le 100
  2. (1717 分):N≤2×103N \le 2 \times 10^3
  3. (77 分):存在一个 xx 满足 ∀0≤i<x\forall 0 \le i < x,A[i]≤A[i+1]A[i] \le A[i + 1] 且 ∀x<i<N\forall x < i < N,A[i]≤A[i−1]A[i] \le A[i - 1]
  4. (1212 分):A[i]≤3A[i] \le 3
  5. (1313 分):W(0,N−1,A[i])≤2W(0,N - 1,A[i]) \le 2(对于所有满足 0≤i≤N−10 \le i \le N - 1 的 ii)
  6. (2222 分):N≤8×104N \le 8 \times 10^4
  7. (1818 分):没有额外限制

评测程序示例

评测程序示例读取如下格式的输入:

  • 第 11 行:NN
  • 第 22 行:A[0] A[1] … A[N−1]A[0]\ A[1]\ \ldots \ A[N - 1]

评测程序示例按照如下的格式打印你的答案:

  • 第 11 行:sequence 的返回值

Hydro 提交说明

只提交实现 sequence 函数的 C++17 源代码,不写 main。平台私有 sequence.h 已包含正式评测入口,并负责原始数据的校验前缀;函数只会接收 N 和 A。附件 3965.zip 中的纯声明头文件与 grader.cpp 用于按上文普通样例格式进行本地联编测试。两套入口调用相同的函数接口。

下载原题的 C++17 头文件、样例交互库和三组样例。