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)$。