遇到一个数组封印的问题，求解答。
Tom 有一个长度为 n 的排列数组 a，即 a 中的每个数字的范围都在 [1,n] 中并且每个数字都不重复。但是现在 Codancer 把整个数组给封印了！现在 Codancer 给了 Tom 一个解封序列 b, 即 bi 代表第 i 次解封 a[b[i]]。接下来Tom每次都会解封一个位置的数字，令L[i]代表第i次解封后所有被解封的数字构成的数组的LIS的长度，现在Codancer想让Tom计算L[1]+L[2]+L[3]+…+L[n] 的值是多少？第一行是一个正整数n，代表a数组和b数组的长度，接下来第一行输入数组a，第二行输入数组 b。(1<=n<=50000)输出 L[1]+L[2]+…+L[n] 的值。
写回答
-
第一步解封后数组为 {4}，因此 L[1]=1第二步解封后数组为 {4,2}，因此 L[2]=1第三步解封后数组为 {4,2,3}，因此 L[3]=2第四步解封后数组为 {4,2,1,3}，因此 L[4]=2因此 L[1]+L[2]+L[3]+L[4]=6
红色数字构成的序列即为 LIS。我们逆向思考，对于给定的数组每次删去一个数，相邻两次操作的答案不会超过 1，对于第i次操作我们随便求一个LIS, 如果第i+1 次操作删除的数字在这个LIS 内，我们就要重新求LIS, 否则答案保持不变，由于随机生成的全排列LIS长度的期望为 sqrt(n)，因此最多计算 sqrt(n) 次 LIS。 因此：输入：4 [4,2,1,3] [1,2,4,3] 输出：6 注： L[1]=1解封后为 {4} L[2]=1解封后为 {4,2} L[3]=2解封后为 {4,2,3} L[4]=2解封后为 {4,2,1,3}2021-12-23 18:39:25赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
