给定数组的所有子数组的MEX和

Question

找到给定数组的所有子数组的MEX之和。数组的MEX (最小除外)是不属于数组的最小非负整数。

例如: MEX为2,2,1是0，因为0不属于数组。MEX为3,1,0,1为2，因为0和1属于数组，但2不属于数组。MEX为0,3, 1，2是4，因为0，1，2和3属于数组，但4不属于数组。值得一提的是，长度为n的数组的MEX总是介于0和n之间。

约束: n<=10^5，ai<=n I认为O(n^2)解不能通过给定的约束。我们需要找到一个O(nlogn)或O(n)解

Answer 1

数组的MEX (最小除外)是不属于数组的最小非负整数。例如：

2,2,1的MEX是0，因为0不属于数组。MEX为3,1,0,1为2，因为0和1属于数组，但2不属于数组。0,3,1,2的MEX是4，因为0,1,2和3属于数组，但4不属于数组。找到非负整数数组的最大可能MEX，这样数组中元素的按位或不超过X。