logo AlgoBeat OnlineJudge
登录 注册

#215482. [KTSC 2026] 平衡序列 / Balanced Sequence

内存限制:1024 MiB 时间限制:4000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

平衡序列的定义如下:

  • 长度为 的序列是平衡序列。
  • 的序列 是平衡序列,当且仅当:
    • 是平衡序列;
    • 是平衡序列;
    • 唯一的最大元素。

给定长度为 的序列 。定义 。例如,若 ,则

次操作,每次操作形如单点修改。操作是累积的。在初始状态和每次操作后,求出满足如下条件的 对数:

  • 是平衡序列。

实现细节

这是一道函数式交互题。你不必,也不应实现 main 函数。

你应当实现以下的函数:

long long initialize(int N, vector<int> A)
  • :序列 的长度。
  • :长度为 的整数数组。
  • 返回初始状态下,满足 为平衡序列的 对数。
  • 该函数仅在运行之初被调用恰好一次。
long long update_sequence(int p, int v)
  • 该函数表示一次令 的操作。
  • 返回操作后,满足 为平衡序列的 对数。
  • 该函数在 initialize 函数调用后,被调用恰好 次。

你的源代码中不应调用任何输入/输出函数。

输入格式

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

  • 行:
  • 行: ...
  • 对于所有
    • 行: (第 update_sequence 的参数)

输出格式

示例评测程序按以下格式输出答案:

  • 行:initialize 的返回值
  • 对于所有
    • 行:第 update_sequence 的返回值

样例

样例输入 1

4 0
1 1 1 1

样例输出 1

4

样例输入 2

12 0
8 9 7 9 2 3 2 8 4 6 2 6

样例输出 2

18

样例输入 3

7 2
1 3 4 4 2 1 6
3 1
3 2

样例输出 3

7
9
8

数据范围与提示

数据范围

子任务

编号 得分 限制
是平衡序列
无额外限制

样例 1

考虑 , , 的情况。 评测程序调用以下函数:

initialize(4, [1, 1, 1, 1])

满足 是平衡序列的 ,因此它应该返回

样例 2

考虑 , , 的情况。 评测程序调用以下函数:

initialize(12, [8, 9, 7, 9, 2, 3, 2, 8, 4, 6, 2, 6])

被调用的函数返回

样例 3

考虑 , , 的情况。 评测程序按顺序调用以下函数:

initialize(7, [1, 3, 4, 4, 2, 1, 6])
update_sequence(3, 1)
update_sequence(3, 2)

被调用的函数分别返回