P7898 [Ynoi2006] 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$。每次原始操作的代价分别计算。
输入格式
无
输出格式
无
说明/提示
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)$。