20260825-奇妙题目 - 题目

题目描述

这是一道函数式交互题。你只需要提交一个 C++ 源文件，实现 solution.h 中声明的四个函数；不要实现 main，也不要进行任何标准输入输出。

评测器会在内存中生成数据并调用相应函数。一个测试点中可能调用同一个函数多次。

#include "solution.h"

long long solve1(int N,
                 const std::vector<int> &U,
                 const std::vector<int> &V);

std::vector<int> solve2(int N,
                        const std::vector<int> &U,
                        const std::vector<int> &V,
                        const std::vector<int> &queryU,
                        const std::vector<int> &queryT);

std::vector<int> solve3(int N,
                        const std::vector<int> &op,
                        const std::vector<int> &x);

long long solve4(const std::vector<int> &A,
                 const std::vector<int> &B,
                 const std::vector<int> &C);

所有点编号和操作参数仍使用题目中的 $1$ 开始编号。std::vector 本身使用 C++ 的 $0$ 开始下标。

接口 1

U 和 V 长度相同，记其长度为 $M$。时刻 $0$ 时有一张包含 $N$ 个点、没有边的无向图。时刻 $i$ 加入边 $(U_{i-1},V_{i-1})$。

保证所有边加入后图连通。请返回

$$ \sum_{1\le i < j \le N} T(i,j) $$

其中 $T(i,j)$ 表示点 $i$ 与点 $j$ 第一次连通的时刻。

限制：

$1\le N\le 5\times10^5$，$N-1\le M\le7.5\times10^5$，且 $M\ge1$；
$1\le U_i,V_i\le N$；允许重边和自环；
一个测试点内各次调用的 $N$ 总和不超过 $5\times10^5$，$M$ 总和不超过 $7.5\times10^5$。

接口 2

U 和 V 描述按顺序加入的 $M$ 条无向边。queryU 和 queryT 长度相同，记为 $Q$。

对于每个 $0\le i < Q$，求加入前 queryT[i] 条边后，点 queryU[i] 所在连通块的大小。返回一个长度恰为 $Q$ 的 vector<int>，答案顺序必须与询问顺序相同。

限制：

$1\le N\le5\times10^5$，$1\le M\le7.5\times10^5$，$1\le Q\le3\times10^5$；
$1\le U_i,V_i,\text{queryU}_i\le N$，$0\le\text{queryT}_i\le M$；允许重边和自环；
一个测试点内各次调用的 $N,M,Q$ 总和分别不超过 $5\times10^5,7.5\times10^5,3\times10^5$。

接口 3

有一个初始全为 $0$、下标为 $1\dots N$ 的序列。op 和 x 长度相同，按顺序描述操作：

op[i] == 1：将位置 x[i] 设为 $1$；
op[i] == 2：求不超过 x[i] 的最大零位置；若不存在则答案为 $0$。

只返回第二类操作的答案，且顺序与第二类操作出现的顺序相同。

限制：

$1\le N\le5\times10^5$，$1\le Q=|op|=|x|\le5\times10^5$；
$op_i\in\{1,2\}$，$1\le x_i\le N$；
一个测试点内各次调用的 $N,Q$ 总和均不超过 $5\times10^5$。

接口 4

A、B、C 是三个长度相同的正整数序列。返回

$$ \max_{1\le l\le r\le N} A_l\cdot B_r\cdot\min_{l\le k\le r}C_k. $$

限制：

$1\le N=|A|=|B|=|C|\le6\times10^5$；
$1\le A_i,B_i,C_i\le10^6$；
一个测试点内各次调用的 $N$ 总和不超过 $6\times10^5$。

调用次数

每个测试点只会调用四个接口中的一个。调用次数不超过 $3\times10^5$，并满足对应接口的各项总和限制。你的程序会在不同测试点中分别接受四种接口的测试，因此必须实现全部四个函数。

样例调用

样例 1：

solve1(5,
       {1, 3, 1, 4, 2, 1, 2},
       {2, 4, 3, 5, 2, 5, 4})

返回 31。

样例 2：

solve2(5,
       {1, 3, 2, 1},
       {2, 4, 3, 1},
       {1, 5, 3, 2, 4, 5},
       {0, 4, 2, 3, 4, 0})

返回 {1, 1, 2, 4, 4, 1}。

样例 3：

solve3(8,
       {1, 2, 1, 1, 2, 1, 2, 1, 2, 2},
       {3, 5, 1, 2, 3, 5, 8, 4, 5, 8})

返回 {5, 0, 8, 0, 8}。

样例 4：

solve4({3, 1, 4, 2, 5, 1},
       {2, 6, 1, 5, 3, 4},
       {4, 2, 5, 1, 3, 6})

返回 60。

Wy Online Judge

WyOJ