题目背景

请勿用 C++14 (GCC 9) 提交。

#include<vector>
std::pair<int, std::vector<int>> complaint(int N, std::vector<int> L, std::vector<int> R);

题目描述

题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T3 「학생들」

在 IOI 大学，学生们不是用名字，而是用考试排名来称呼彼此。这所大学有 $N$ 名学生，对于每个 $i$ $(0 \leq i \leq N-1)$，第 $i$ 名学生在期中考试中排名第 $i+1$。

为了准备期末考试，学生们自发组成了辅导小组。每个辅导小组可以用两个整数 $0 \leq L \leq R \leq N-1$ 表示，表示编号在 $L$ 到 $R$ 之间的学生不在这个小组中，其他学生都在这个小组中。

某天早晨，IOI 大学的所有学生都收到了一封邮件，通知他们至少存在一个辅导小组。这一天被称为第 $1$ 天早晨。从第 $d \geq 1$ 天晚上开始，以下情况会发生：

• 如果某个学生在第 $d$ 天早晨之后推断出存在一个不包含自己的辅导小组，他会感到不公平，并在第 $d$ 天晚上结束前提交投诉。一旦投诉提交，所有辅导小组的活动将在第 $d+1$ 天早晨之前结束。
• 如果没有学生推断出存在一个不包含自己的辅导小组，则没有投诉提交，辅导小组的活动会在第 $d+1$ 天早晨继续。所有学生都会意识到没有人在第 $d$ 天提交投诉。

除此之外，学生们不会以任何方式共享信息。也就是说，他们只能知道自己所在的辅导小组及其成员，以及是否有投诉提交。学生们总是根据自己掌握的信息进行推断，不会推断出可能错误的结论。

你是 IOI 大学所有学生的朋友，知道所有辅导小组及其成员。当给定 $M$ 个辅导小组的信息时，请编写一个程序，找出投诉提交的日期 $k$ 以及在第 $k$ 天提交投诉的学生编号。如果永远没有投诉提交，则返回 -1。

请注意，只有你作为外部人知道所有辅导小组的信息，包括小组的数量 $M$、每个小组的成员、问题的整体限制和部分限制等。学生们对此一无所知。

你需要实现以下函数：

pair<int, vector<int>> complaint(int N, vector<int> L, vector<int> R);

• L, R：大小为 $M$ 的整数数组。对于每个 $i$ $(0 \leq i \leq M-1)$，第 $i$ 个辅导小组由编号小于 $L[i]$ 或大于 $R[i]$ 的学生组成。
• 该函数返回一个由整数 $k$ 和一个大小不超过 $N$ 的整数数组 $V$ 组成的对。$k$ 是投诉提交的日期，$V$ 是在第 $k$ 天提交投诉的学生编号，按升序排列。如果永远没有投诉提交，则 $k$ 为 $-1$，$V$ 为空数组。

注意，提交的代码中不应包含任何输入输出操作。

输入格式

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N\,M$
• 第 $2+i$ $(0 \leq i \leq M-1)$ 行：$L[i]\,R[i]$

输出格式

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

• 第 $1$ 行：函数 complaint 返回的值 $k$
• 第 $2$ 行：函数 complaint 返回的数组 $V$ 的元素，以空格分隔

6 3
1 4
2 5
3 3

1
3

10 4
1 4
4 7
8 9
2 6

2
4 8 9

5 1
0 4

1
0 1 2 3 4

提示

样例 1 解释

考虑 $N=6, M=3, L=[1,2,3], R=[4,5,3]$ 的情况。

评测程序将调用如下函数：

complaint(6, [1, 2, 3], [4, 5, 3]);

由于第 $3$ 号学生被所有辅导小组排除在外，他会在第一天立即提交投诉。其他学生在第一天不会提交投诉。因此，函数应返回 (1, [3])。

数据范围

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

• $1 \leq N \leq 2.5\cdot 10^5$
• $1 \leq M \leq 2.5\cdot 10^5$
• 对于每个 $i$ $(0 \leq i \leq M-1)$，$0 \leq L[i] \leq R[i] \leq N-1$

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

子任务	分值	附加限制
$1$	$12$	$N, M \leq 10$
$2$	$6$	对于每个 $i$ $(0 \leq i \leq M-1)$，$L[i]=R[i]$
$3$	$15$	$N, M \leq 2500$
$4$	$10$	对于每个 $i$ $(0 \leq i, j \leq M-1)$，区间 $[L[i], R[i]]$ 和 $[L[j], R[j]]$ 互不相交或包含彼此。 即如果 $L[i] < L[j]$，则 $R[i] < L[j]$ 或 $R[j] \leq R[i]$
$5$	$18$	对于每个 $i$ $(0 \leq i \leq M-2)$，$L[i] < L[i+1], R[i] < R[i+1]$
$6$	$39$	无附加限制