추이 계수-hdu-4747-Mex

제목 링크:
http://acm.hdu.edu.cn/showproblem.php?pid=4747
제목 의 대의:
n 개 수 를 주 고 모든 구간 에 나타 나 지 않 은 최소 비 마이너스 정수 와.
문제 풀이 방향:
먼저 대신 블 로그 에 감 사 드 립 니 다.
다시 한번 말씀 드 리 겠 습 니 다.
우선 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
",i,tt);

            ans+=tt;

        }

        printf("%I64d
",ans);

   }

   return 0;

}