QOJ.ac

QOJ

Time Limit: 15 s Memory Limit: 1024 MB Total points: 100 Interactive

# 7447. wcirq

统计

这是一道交互题。

你需要进行 $n$ 个原始操作,对一个序列进行维护。初始序列为空。

第 $i$ 个原始操作给出整数 $x_i,\;l_i,\;r_i$,表示在序列的第 $x_i$ 个位置前插入元素 $i$(若 $x_i=i$ 则表示在序列末尾插入),然后查询序列中第 $l_i,\;l_{i+1},\;\dots,\;r_i$ 个元素构成的集合。

为了回答这些查询,你可以操作若干个集合。这些集合初始为空,编号为 $1$ 到 $2\times 10^7$ 的整数。

你可以花费 $1$ 个单位的第一类代价进行插入操作:在编号为 $x$ 的集合中插入元素 $y$,在回答第 $i$ 个原始操作的查询前,需要保证 $1\le y\le i$。

你可以花费 $k$ 个单位的第二类代价回答查询:选取编号为 $a_1,\;a_2,\;\dots,\;a_k$ 的集合,要求这些集合互不相交,且并集是查询的答案。

每次原始操作后,插入操作和回答查询的第一类/第二类代价不能超过当前子任务的代价上限 $m_1,\;m_2$。每次原始操作的代价分别计算。

实现细节

你需要实现函数:

void solve(int x,int l,int r);

对于每次原始操作,这个函数被调用一次,参数 x l r 对应 $x_i,\;l_i,\;r_i$。

你可以调用函数:

void op1(int x,int y);
void op2(int k);

调用 op1 表示执行一次插入操作;

对 $a_1,\dots,a_k$ 依次调用 op2 表示回答查询。

在提交的代码中,你需要声明这两个函数。

样例数据

假设交互库调用了3次 solve 函数如下:

solve(1,1,1);
solve(1,2,2);
solve(2,1,3);

以下给出了一种符合要求的对 op1op2 的调用:

op1(1,1);
op2(1);

此时序列为 $(1)$,编号1的集合为 $\{1\}$,第1次 solve 函数调用返回;

op2(1);

此时序列为 $(2,1)$,编号1的集合为 $\{1\}$,第2次 solve 函数调用返回;

op1(1,2);
op1(2,3);
op2(2);
op2(1);

此时序列为 $(2,3,1)$,编号1的集合为 $\{1,2\}$,编号2的集合为 $\{3\}$,第3次 solve 函数调用返回。

子任务

Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078&nzhtl1477

对于 $100\%$ 的数据,满足 $1\le n\le 10^6$;$1\le x_i\le i$;$1\le l_i\le r_i\le i$;

你输出的插入操作或回答查询中,集合编号在范围 $1$ 到 $2\times 10^7$ 内,插入操作的 $y$ 必须是序列中已有的元素。

子任务1(10分):保证 $1\le n\le 10^3$;

子任务2(10分):保证 $l_i=1,\;r_i=i$;

子任务3(10分):保证 $x_i=i$;

子任务4(20分):保证 $1\le n\le 10^4$;

子任务5(10分):保证 $1\le n\le 10^5$;

子任务6(20分):数据随机生成,其中 $n=10^6$, $(l_i,r_i)$ 和 $x_i$ 分别在所有可能的情况中随机选取。

子任务7(20分):无特殊限制。

对子任务6,$(m_1,m_2)=(64,64)$;

对其余子任务,$(m_1,m_2)=(64,256)$。