E - Mex

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=216#problem/E
また線分樹神題です.
非負のシーケンスについてmex(i,j)を区間[i,j]内に最小の正の整数が現れないように定義した.(1<=i<=j<=n)を満たすすべてのmex(i,j)の和を求める.
シーケンス1 2 0 4 6 3 5 7 1 4 8を例にとると,まずi=1のmex(1,j),i=2のmex(2,j)を
i = 1     0 0 3 3 3 5 7 8 8 8 8 8 9
i = 2        0 1 1 1 1 1 1 8 8 8 8 9
mex(2,j)とmex(1,j)との関係は,1番目の1(a[1])と2番目の1(a[9])との間のmex(1,j)>1(a[1])の数がmex(2,j)ではいずれも1となり,残りのmex(2,j)は変わらないことがわかる.したがって,1(a[1])になる区間lとrを見つけ,この区間の値和を更新すればよい.
また、すべての固定iに対してmex(i,j)がインクリメントされていることが判明し、この性質に基づいて区間の左端点l、すなわち、最初のmex値がa[1]より大きい位置を見つけることができ、rは、各位置の数を記録するnext配列を設定することができ、r=next[i]−1である.
したがって,mex(1,j)を初期化してから,以降のmex(i,j)を順次求め,区間の和最大値をセグメントツリーで維持する.

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
//#define LL long long
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 200010;

struct node
{
    int l,r;
    int lazy; //lazy             		
    LL sum; //    
    LL mx;//      
}tree[maxn*4];

int a[maxn];
int next[maxn];
int mex[maxn];
map<int,int>M;

void push_up(int v)
{
    if(tree[v].l == tree[v].r) return;
    tree[v].mx = max(tree[v*2].mx,tree[v*2+1].mx);
    tree[v].sum = tree[v*2].sum + tree[v*2+1].sum;
}

void push_down(int v)
{
    if(tree[v].l == tree[v].r || tree[v].lazy == 0)
        return;
    tree[v*2].lazy = tree[v*2+1].lazy = 1;
    tree[v*2].mx = tree[v*2+1].mx = tree[v].mx;
    tree[v*2].sum = tree[v].mx * (tree[v*2].r - tree[v*2].l + 1);
    tree[v*2+1].sum = tree[v].mx * (tree[v*2+1].r - tree[v*2+1].l + 1);
    tree[v].lazy = 0;
}

void build(int v, int l, int r)
{
    tree[v].l = l;
    tree[v].r = r;
    tree[v].lazy = 0;
    if(l == r)
    {
        tree[v].sum = mex[tree[v].l];
        tree[v].mx = mex[tree[v].l];
        return;
    }
    int mid = (l+r)>>1;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
    push_up(v);
}

//  mex      a[i]   
int get(int v, int key)
{
    if(tree[v].l == tree[v].r)
        return tree[v].l;
    push_down(v);
    if(key < tree[v*2].mx)
        return get(v*2,key);
    else return get(v*2+1,key);
}

void update(int v, int l, int r, int key)
{
    if(tree[v].l == l && tree[v].r == r)
    {
        tree[v].mx = key;
        tree[v].lazy = 1;
        tree[v].sum = key * (tree[v].r - tree[v].l + 1);
        return;
    }
    push_down(v);
    int mid = (tree[v].l + tree[v].r) >> 1;
    if(r <= mid)
        update(v*2,l,r,key);
    else if(l > mid)
        update(v*2+1,l,r,key);
    else
    {
        update(v*2,l,mid,key);
        update(v*2+1,mid+1,r,key);
    }
    push_up(v);
}

int main()
{
    int n,Min;
    while(~scanf("%d",&n)&&n)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        M.clear();
        Min = 0;
        for(int i = 1; i <= n; i++)
        {
            M[a[i]] = 1;
            while(M.find(Min) != M.end())
                Min++;
            mex[i] = Min;
        }

        M.clear();
        for(int i = n; i >= 1; i--)
        {
            if(M.find(a[i]) == M.end())
                next[i] = n+1; //next[i]   next[a[i]]
            else next[i] = M[a[i]];
            M[a[i]] = i;
        }

        build(1,1,n);
        LL sum = 0;
        for(int i = 1; i <= n; i++)
        {
            sum += tree[1].sum;
            if(tree[1].mx > a[i])
            {
                int l = get(1,a[i]);
                int r = next[i];
                if(l < r)
                    update(1,l,r-1,a[i]);
            }
            update(1,i,i,0);
        }
        printf("%I64d
",sum);
    }
    return 0;
}