HBC237670[SDOI2016]排列计数,组合数学,排列组合“经典”问题题解（mmm次查询区间的mex值）

淫家是湿人算法基础篇 2023-11-10 00:23:02 30 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

给定一个序列，mmm 次查询区间的 mex 值，mex 表示最小的没出现过的自然数，n,m≤105n,mle 10^5n,m≤105，显然可以使用经典算法轻易解决这个经典问题，现在蒟蒻 djy 魔改了一下它，给定一个 000 到 n1n-1n1 的排列，mmm 次查询区间的 mex 值，但是 n,mn,mn,m 变大了，你能帮帮他吗?n,m≤107n,mle 10^7n,m≤107，输入数据在程序内生成。

给定一个序列，mmm 次查询区间的 mex 值，mex 表示最小的没出现过的自然数，n,m≤105n,mle 10^5n,m≤105。显然可以使用经典算法轻易解决这个经典问题。现在蒟蒻 djy 魔改了一下它，给定一个 000 到 n−1n-1n−1 的排列，mmm 次查询区间的 mex 值，但是 n,mn,mn,m 变大了，你能帮帮他吗? n,m≤107n,mle 10^7n,m≤107，输入数据在程序内生成。