遞推計數-hdu-4747-Mex

題目大意：   給n個數，求所有區間內沒有出現的最小非負整數和。   解題思路：   首先感謝大神博客：http://www.cnblogs.com/xin-hua/p/3325154.html可以解釋的太少了。   我再解釋一遍。   首先要明白，以i結束的所有區間的值的和記為f[i]肯定不超過以i+1結束的所有區間的值的和記為f[i+1]。   所以可以根據f[i]間接推出f[i+1]，記第i個數為sa[i],顯然只用考慮大於等於sa[i]的數j對f[i]=f[i-1]+？的影響,。如果j出現在1~i-1區間中，比較j最晚出現的位置與覆蓋完全的1~j-1的最小位置的較小位置k，那麼區間j的前一次出現的位置到k位置這個區間內所有點到i位置的值都+1.   這樣逐次累加，直到不影響為止。   代碼：    

#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#include<ctime>  
#define eps 1e-6  
#define INF 0x3fffffff  
#define PI acos(-1.0)  
#define ll __int64  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 210000  
  
int sa[Maxn],pos[Maxn],full[Maxn];  
  
int main()  
{  
   //freopen("in.txt","r",stdin);  
   //freopen("out.txt","w",stdout);  
   int n;  
  
   while(scanf("%d",&n)&&n)  
   {  
       for(int i=1;i<=n;i++)  
            scanf("%d",&sa[i]);  
        memset(pos,0,sizeof(pos));  
        memset(full,0,sizeof(full));  
        int last;  
        ll tt=0,ans=0;  
  
        for(int i=1;i<=n;i++)  
        {  
            if(sa[i]<n)//  
            {  
                last=pos[sa[i]];//前一個sa[i]的最晚位置  
                pos[sa[i]]=i; //最晚位置  
                for(int j=sa[i];j<n;j++)  
                {  
                    if(j) //考慮j對前面區間的影響  
                        full[j]=min(full[j-1],pos[j]); //  
                    else  
                        full[j]=i;  
                    if(full[j]>last)  
                        tt+=full[j]-last; //last+1到full[j]區間內所有點到i的值+1，逐次累加  
                    else  
                        break;  
                }  
            }  
            printf("i:%d %I64d\n",i,tt);  
            ans+=tt;  
        }  
        printf("%I64d\n",ans);  
   }  
   return 0;  
}