HDU 4747 Mex ( 线段树好题 + 思路 )

参考：http://www.cnblogs.com/oyking/p/3323306.html

相当不错的思路，膜拜之~

个人理解改日补充。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define lc rt << 1
#define rc rt << 1 | 1
#define LL long long int

using namespace std;

const int MAXN = 200010;

struct node
{
    int pos;
    int next;
};

LL sum[ MAXN << 2 ];
int maxi[ MAXN << 2 ];
int mini[ MAXN << 2 ];
int N;
int num[MAXN];
node D[ MAXN << 1 ];
int head[MAXN];
int EdgeN;

void AddEdge( int u, int v )
{
    D[EdgeN].pos = v;
    D[EdgeN].next = head[u];
    head[u] = EdgeN++;
    return;
}

void PushDown( int rt, int m )
{
    if ( maxi[rt] == mini[rt] )
    {
        maxi[lc] = mini[lc] = maxi[rt];
        sum[lc] = (LL)maxi[rt]*( m - ( m >> 1 ) );
        maxi[rc] = mini[rc] = mini[rt];
        sum[rc] = (LL)maxi[rt]*( m >> 1 );
    }
    return;
}

void PushUp( int rt )
{
    sum[rt] = sum[lc] + sum[rc];
    maxi[rt] = max( maxi[lc], maxi[rc] );
    mini[rt] = min( mini[lc], mini[rc] );
    return;
}

void build( int l, int r, int rt )
{
    if ( l == r )
    {
        sum[rt] = maxi[rt] = mini[rt] = N - l + 1;
        return;
    }
    int m = ( l + r ) >> 1;
    build( lson );
    build( rson );
    PushUp( rt );
    return;
}

void update( int L, int R, int val, int l, int r, int rt )
{
    if ( L <= l && r <= R && mini[rt] >= val )
    {
        sum[rt] = (LL)val*(r - l + 1);
        maxi[rt] = mini[rt] = val;
        return;
    }
    if ( l == r ) return;
    PushDown( rt, r - l + 1 );
    int m = ( l + r ) >> 1;
    if ( L <= m && maxi[lc] > val ) update( L, R, val, lson );
    if ( R > m && maxi[rc] > val )  update( L, R, val, rson );
    PushUp( rt );
    return;
}

int main()
{
    while ( scanf( "%d", &N ) == 1 && N )
    {
        for ( int i = 1; i <= N; ++i )
            scanf( "%d", &num[i] );
        memset( head, -1, sizeof(int)*(N+2) );
        EdgeN = 1;
        for ( int i = N; i > 0; --i )
        {
            if ( num[i] <= N )
                AddEdge( num[i], i );
        }
        build( 1, N, 1 );
        LL ans = 0;
        for ( int i = 0; i <= N && sum[1]; ++i )
        {
            int pre = 0;
            for ( int j = head[i]; j != -1; j = D[j].next )
            {
                update( pre + 1, D[j].pos, N - D[j].pos + 1, 1, N, 1 );
                pre = D[j].pos;
                //printf("num=%d pos=%d
", i, D[j].pos );
            }
            update( pre + 1, N, 0, 1, N, 1 );
            ans += sum[1];
            //printf( "ans=%I64d
", ans );
        }
        printf("%I64d
", ans );
    }
    return 0;
}