AdditionalFile5618.zip

#5618. 「KTSC 2026 R1」平衡序列

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "balance.h"。

题目描述

题目译自 2026년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T1 「균형잡힌 수열」

我们将符合以下条件的序列定义为平衡序列：

• 长度为 $1$ 的所有序列都是平衡序列。
• 长度为 $2k+1$ 的序列 $S = [S_0, \ldots, S_{2k}]$ 如果满足以下条件，则它是平衡序列：
  • $[S_0, S_1, \ldots, S_{k-1}]$ 是平衡序列。
  • $[S_{k+1}, S_{k+2}, \ldots, S_{2k}]$ 是平衡序列。
  • $S_k$ 是序列 $S$ 所有元素中的唯一最大值。

给定一个由 $N$ 个整数组成的序列 $A$。$A[i \ldots j]$ 表示由序列 $A$ 的第 $i$ 个元素到第 $j$ 个元素构成的长度为 $j-i+1$ 的序列。例如，当 $A = [3, 5, 7, 2, 9]$ 时，$A[1 \ldots 3]$ 是 $[5, 7, 2]$，而 $A[4 \ldots 4]$ 是 $[9]$。

系统将给出 $Q$ 个查询。每个查询都是修改序列中特定元素的操作，且这些操作是累加的。在初始状态以及每次查询执行后，请你求出满足 $0 \leq i \leq j \leq N-1$ 且 $A[i \ldots j]$ 为平衡序列的整数对 $(i, j)$ 的总数。

实现细节

你需要实现以下函数：

long long initialize(int N, vector<int> A)

• $N$：序列 $A$ 的长度。
• $A$：长度为 $N$ 的整数数组。
• 该函数应返回满足 $0 \leq i \leq j \leq N-1$ 且 $A[i \ldots j]$ 为平衡序列的整数对 $(i, j)$ 的总数。
• 该函数仅在初期被调用一次。

long long update_sequence(int p, int v)

• 该函数表示将 $A[p]$ 的值修改为 $v$ 的查询。
• 该函数应返回 $A[p]$ 修改后，满足 $0 \leq i \leq j \leq N-1$ 且 $A[i \ldots j]$ 为平衡序列的整数对 $(i, j)$ 的总数。
• 该函数将在调用 initialize 函数之后被调用共 $Q$ 次。

在提交的源代码中，你不应在任何地方执行输入或输出函数。

样例 1

假设 $N=4, Q=0, A=[1, 1, 1, 1]$。 评测程序将调用如下函数：

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

由于 $A[i \ldots j]$ 为平衡序列的 $(i, j)$ 列表仅为 $(0,0), (1,1), (2,2), (3,3)$，因此应返回 $4$。

样例 2

假设 $N=12, Q=0, A=[8, 9, 7, 9, 2, 3, 2, 8, 4, 6, 2, 6]$。 评测程序将调用如下函数：

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

该函数调用应返回 $18$。

样例 3

假设 $N=7, Q=2, A=[1, 3, 4, 4, 2, 1, 6]$。 评测程序将按顺序调用如下函数：

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

这些函数调用应依次返回 $7, 9, 8$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^{5}$
• $0 \leq Q \leq 10^{5}$
• 对于所有 $i$，满足 $1 \leq A[i] \leq 10^{9}$ $(0 \leq i \leq N-1)$
• 对于所有 update_sequence 的调用，满足 $0 \leq p \leq N-1, 1 \leq v \leq 10^{9}$

详细子任务附加限制及分值如下表所示。

示例评测程序

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

• 第一行：$N \ Q$
• 第二行：$A[0] \ A[1] \ \ldots \ A[N-1]$
• 对于每个 $1 \leq k \leq Q$：
  • 第 $2+k$ 行：$p \ v$（第 $k$ 次 update_sequence 的参数）

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

• 第一行：initialize 的返回值
• 对于每个 $1 \leq k \leq Q$：
  • 第 $1+k$ 行：第 $k$ 次 update_sequence 的返回值