AdditionalFile5621.zip

#5621. 「KTSC 2026 R1」精彩区间 2

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

注意事项

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

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

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

题目描述

题目译自 2026년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T4 「멋진 구간 2」

英雨拥有两个长度为 $N$ 的整数数组 $A$ 和 $B$。对于所有 $0 \leq i \leq N-1$，均满足 $A[i] \leq B[i]$。

如果一个区间 $[l, r]$ 满足以下所有条件，则称其为精彩区间：

• $l, r$ 为整数。
• $0 \leq l \leq r \leq N-1$。
• 可以通过对数组 $[A[l], \dots, A[r]]$ 重复执行以下操作，使其变为 $[B[l], \dots, B[r]]$：
  • 设当前数组为 $X = [X[0], X[1], \dots, X[r-l]]$。
  • 选择两个满足 $X[i] = X[j]$ 的不同下标 $0 \leq i, j \leq r-l$，并将 $X[i]$ 的值增加 $1$。

英雨很想知道哪些区间是精彩区间。

具体来说，英雨共有 $Q$ 个编号为从 $0$ 到 $Q-1$ 的询问，这些询问由长度为 $Q$ 的整数数组 $L$ 和 $R$ 表示。第 $j$ $(0 \leq j \leq Q-1)$ 个询问是判断区间 $[L[j], R[j]]$ 是否为精彩区间。你需要编写一个程序来回答英雨的这些询问。

实现细节

你需要实现以下函数：

vector<int> array_operation(vector<int> A, vector<int> B, vector<int> L, vector<int> R)

• $A, B$：大小为 $N$ 的整数数组。
• $L, R$：大小为 $Q$ 的整数数组。
• 该函数应返回一个大小为 $Q$ 的整数数组 $S$。如果 $[L[j], R[j]]$ 是精彩区间，则 $S[j]$ 应为 $1$；否则，$S[j]$ 应为 $0$（$0 \leq j \leq Q-1$）。
• 该函数仅会被调用一次。

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

样例 1

考虑如下调用： array_operation([2, 1, 1, 2], [2, 1, 3, 3], [0, 0, 1], [1, 3, 3])

• $[0, 1]$ 是精彩区间。因为两个数组 $[A[0], A[1]]$ 和 $[B[0], B[1]]$ 完全相同。
• $[0, 3]$ 是精彩区间。因为在 $[2, 1, 1, 2]$ 上执行如下操作可以使其变为 $[2, 1, 3, 3]$：
  • 选择 $i=3, j=0$ 执行操作。操作后数组变为 $[2, 1, 1, 3]$。
  • 选择 $i=2, j=1$ 执行操作。操作后数组变为 $[2, 1, 2, 3]$。
  • 选择 $i=2, j=0$ 执行操作。操作后数组变为 $[2, 1, 3, 3]$。
• $[1, 3]$ 不是精彩区间。可以证明，无论如何在 $[1, 1, 2]$ 上执行操作，都无法使其变为 $[1, 3, 3]$。

因此，函数应返回 $[1, 1, 0]$。

样例 2

考虑如下调用： array_operation([1, 2, 1, 2, 1], [2, 3, 1, 4, 2], [0, 0, 1, 1, 2], [2, 4, 3, 4, 3])

在所有给定的区间中，精彩区间包括 $[0, 2], [0, 3], [0, 4], [1, 4], [2, 2]$。因此，函数应返回 $[1, 1, 0, 1, 0]$。

数据范围与提示

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

• $1 \leq N, Q \leq 250000$
• 对于所有 $i$，满足 $1 \leq A[i] \leq B[i] \leq 10^{9}$ ($0 \leq i \leq N-1$)
• 对于所有 $j$，满足 $0 \leq L[j] \leq R[j] \leq N-1$ ($0 \leq j \leq Q-1$)

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

示例评测程序

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

• 第一行包含两个整数 $N \ Q$。
• 接下来的 $N$ 行中，第 $2+i$ 行包含 $A[i] \ B[i]$ ($0 \leq i \leq N-1$)。
• 接下来的 $Q$ 行中，第 $2+N+i$ 行包含 $L[i] \ R[i]$ ($0 \leq i \leq Q-1$)。

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

• 第一行输出 array_operation 的返回值。