Mex

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 3056 Accepted Submission(s): 1006

Problem Description

Mex is a function on a set of integers, which is universally used for impartial game theorem. For a non-negative integer set S, mex(S) is defined as the least non-negative integer which is not appeared in S. Now our problem is about mex function on a sequence.

Consider a sequence of non-negative integers {ai}, we define mex(L,R) as the least non-negative integer which is not appeared in the continuous subsequence from aL to aR, inclusive. Now we want to calculate the sum of mex(L,R) for all 1 <= L <= R <= n.

Input

The input contains at most 20 test cases.
For each test case, the first line contains one integer n, denoting the length of sequence.
The next line contains n non-integers separated by space, denoting the sequence.
(1 <= n <= 200000, 0 <= ai <= 10^9)
The input ends with n = 0.

Output

For each test case, output one line containing a integer denoting the answer.

Sample Input

3
0 1 3
5
1 0 2 0 1
0

Sample Output

5
24

Hint

For the first test case:
mex(1,1)=1, mex(1,2)=2, mex(1,3)=2, mex(2,2)=0, mex(2,3)=0,mex(3,3)=0.
1 + 2 + 2 + 0 +0 +0 = 5.

Source

2013 ACM/ICPC Asia Regional Hangzhou Online

Recommend

liuyiding | We have carefully selected several similar problems for you: 6022 6021 6020 6019 6018

题意：Mex(l,r) 求的是[l,r]区间内所有数的集合里没有出现过的最小的数字，即博弈里的mex。现在给出一个序列[1,n]，求解所有$1 \le l \le r\le n$ 的[l,r]中的mex[l,r]的和。

首先我们将区间右端点统一为k，用num[k]存k这个位置对应的数字。即我们处理到k这个端点时，我们处理的是所有$[l,k] （1 \le l \le k）$的mex。此时我们只需要for一遍然后对应处理k就行。

那怎么加速k这个端点的处理呢？我们用t[l] 表示[l,k] 中所有数的集合set从零开始连续的最大的数，即mex-1，那么假如我们的序列为6 0 3 2 0 1 0 ，处理到最后一个数k=7，对应的t为 3 3 3 2 1 1 0,可以看出t为一个非递减序列,因此我们用aft[o]存t中数字o连续序列的最后一个位置，例如aft[1]=6。

我们可以将这个问题化为区间右端点扩张的问题，每次更新对应一些区间的右端点扩张。我们还用last[o]存数字o最后出现的位置。可以看出我们每到一个新端点k，它对应的数字为knum，影响的t区间为大于等于knum的数字所在的区间，准确的说是s大于等于knum并且aft[s]==aft[knum]的数字所在的区间，因为一旦aft[s]<aft[knum]那么限制他的右端点扩张的数字就不是knum了，而是大于knum的数字。所以我们需要更新这些数字所在区间右端点，并且从小到大更新，设更新的区间右端点最大值为maxn。由于这些数字区间右端点还受aft[knum-1]限制，初始maxn=aft[knum-1]。然后每个数字s的右端点最大值为min（aft[knum-1],last[knum]，last[knum+1]......last[s]）（最左端的端点限制扩张）。至此我们快速的更新t区间。另外我们用all存现在l∈[1,k] 所有[l,k]mex的和，那么每次更新右端点就需要给all加上更新的区间的长度作为扩张对mex的贡献。最后我们把所有的all加起来就是答案。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #define clr(x) memset(x,0,sizeof(x))

 #define LL long long

 using namespace std;

 int a[],aft[],last[];

 LL ans,all;

 int min(int a,int b)

 {

     return a<b?a:b;

 }

 int main()

 {

     int n,m,k,dk,maxn;

     while(scanf("%d",&n)== && n!=)

     {

         ans=;

         all=;

         clr(last);

         clr(aft);

         for(int i=; i<=n; i++)

         {

             scanf("%d",&a[i]);

             if(a[i]>=n)

             {

                 ans+=all;

                 continue;

             }

             last[a[i]]=i;

             if(a[i]>)

             {

                 maxn=aft[a[i]-];

             }

             else

             {

                 maxn=i;

             }

             k=a[i];

             dk=aft[k];

             while(aft[k]==aft[k+])

             {

                 maxn=min(maxn,last[k]);

                 if(maxn==dk)

                     break;

                 all+=(LL)(maxn-aft[k]);

                 aft[k]=maxn;

                 k++;

             }

             maxn=min(maxn,last[k]);

             all+=(LL)(maxn-aft[k]);

             aft[k]=maxn;

             ans+=all;

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

hdu 4747 Mex( 线段树？不，区间处理就行（dp？））

Mex

最新文章

热门文章

巴特西

hdu 4747 Mex( 线段树？ 不，区间处理就行（dp？））

Mex

最新文章

热门文章

hdu 4747 Mex( 线段树？不，区间处理就行（dp？））