当前没有测试数据。

题目描述

这是一道交互题，请引用：

#include "ds.h"

你会收到两个整数 $n,q$，以及 $q$ 个区间

$$[l_1,r_1],[l_2,r_2],\ldots,[l_q,r_q].$$

保证

$$1\le l_i\le r_i\le n,$$

且每个二元组 $(l_i,r_i)$ 都是在所有满足 $1\le l\le r\le n$ 的二元组中随机生成的。

你需要维护一个集合

$$S\subseteq\{1,2,\ldots,n\},$$

初始时 $S=\varnothing$。你可以使用下面五种操作。

void add(int x);

向 $S$ 中添加整数 $x$。你必须保证

$$1\le x\le n,\qquad x\notin S.$$

void del(int x);

从 $S$ 中删除整数 $x$。你必须保证

$$1\le x\le n,\qquad x\in S.$$

void revoke();

设最近一次被加入 $S$，且尚未被删除或撤销的元素为 $x$，则将 $x$ 从 $S$ 中删除。你必须保证存在这样的元素。

void clear();

清空 $S$，即令

$$S=\varnothing.$$

void report(int k);

向交互库报告已经形成了第 $k$ 个区间。调用时必须恰好满足

$$S=\{l_k,l_k+1,\ldots,r_k\}.$$

当所有区间均被恰好报告一次时，视为完成任务。

实现方式

你需要实现下面的函数：

void solve(
    int n,
    int q,
    vector<int> l,
    vector<int> r
);

数组 l 和 r 的下标范围均为 $0$ 到 $q-1$。

子任务与评分

设 $C_1,C_2,C_3,C_4,C_5$ 分别表示 add、del、revoke、clear、report 五种操作的调用次数。

你必须保证：

$$C_4\le n,\qquad C_5=q.$$

子任务编号	分值	$n\le$	$q\le$	$C_1\le$	$C_2\le$	$C_3\le$
1	10	$1000$		$10^6$	$0$	$0$
2	20	$5\times 10^4$	$10^5$	$35000000$	$35000000$
3					$0$	$35000000$
4	50			$6\times 10^7$		$0$

对于前三个子任务，只要对应操作次数均不超过限制，即可获得该子任务满分；否则该子任务得 $0$ 分。

对于子任务 4：

• 若 $C_1\le 30000000$，获得该子任务满分，即 $50$ 分；
• 若 $30000000<C_1\le 60000000$，获得的分数为

$$\left\lfloor 50\times\left(1-\frac{C_1-30000000}{30000000}\right) \right\rfloor;$$

• 若 $C_1>60000000$，或不满足其他限制条件，则获得 $0$ 分。