P11347 [KTSC 2023 R2] 学生

**请勿用 C++14 (GCC 9) 提交。** ```cpp #include std::pair complaint(int N, std::vector L, std::vector R); ```

**题目译自 [2023년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2023/) T3 「[학생들](https://assets.ioikorea.kr/ioitst/2023/2/students/students_statement.pdf)」** 在 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$、每个小组的成员、问题的整体限制和部分限制等。学生们对此一无所知。 你需要实现以下函数： ```cpp pair complaint(int N, vector L, vector 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$ 的元素，以空格分隔

### 样例 1 解释 考虑 $N=6, M=3, L=[1,2,3], R=[4,5,3]$ 的情况。 评测程序将调用如下函数： ```cpp 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$ | 无附加限制 |