Brief description:

。。。给定一个长度为 n 的非负数列。。定义 mex(l, r) 为 l，r 区间里最小的没有出现的数字。
。。求所有 mex(l, r) 的和。。。

Analysis:

..。直接合并区间难以进行时。。利用离线先固定一个端点。。沿着另一个端点扫应该是接下来第一个要想的方法了。。。
。艹。。我是傻逼么。。

。。先 O(n) 搞出 mex1[i] 表示初始的 mex(1, i)。。这个是单调递增的。。。
。。。再 O(n) 搞出每个 nxt[i] 。。表示右边第一个和 i 相同的位置。。（如果没有则等于 n+1。。。。
。。。接着沿着左侧开始删除。。删除前要统计出以这个点为左端点的所有 mex。 。。
。。。考虑删除 a[i]。。那么将 i+1 到 nxt[i]-1 之间。。mex 大于 a[i] 的全设置成 a[i]。即可。。。

。。。于是我们需要维护。。。区间求和。。。以及区间赋值成至多 a[i]。。。这是一个线段树的 Open Problem 。。。（至少对我而言。？。。
。。。进一步分析发现 mex 始终是单调递增的。。
。。。因此将 i+1 到 nxt[i]-1 赋值到至多 a[i]。。就是将第一个大于 a[i] 的位置 到 nxt[i] -1 赋值到 a[i] 即可。。而这是一个线段树入门级别的操作。。。

const int N = 200009, NN = 4*N;
int A[N], C[N], nxt[N], mex1[N];
int n;

LL ss[NN]; int mx[NN]; bool dd[NN]; int a, b, c;

#define root 1, 1, n
#define lx (x << 1)
#define rx (lx | 1)
#define ml (l + r >> 1)
#define mr (ml + 1)
#define len (r - l + 1)
#define xc x, l, r
#define lc lx, l, ml
#define rc rx, mr, r

inline void Apply_Cov(int x, int l, int r, int val){
    mx[x] = val, ss[x] = (LL) len * val, dd[x] = 1;
}

void Release(int x, int l, int r){
    if (dd[x]){
        Apply_Cov(lc, mx[x]), Apply_Cov(rc, mx[x]);
        dd[x] = 0;
    }
}

void Update(int x){
    mx[x] = max(mx[lx], mx[rx]);
    ss[x] = ss[lx] + ss[rx];
}

void Insert(int x, int l, int r){
    if (b < l || r < a) return;
    if (a <= l && r <= b){
        Apply_Cov(xc, c);
    }
    else{
        Release(xc);
        Insert(lc), Insert(rc);
        Update(x);
    }
}

int Upper_Bound(int x, int l, int r){
    if (l == r) return l;
    else{
        Release(xc);
        return mx[lx] > c ? Upper_Bound(lc) : Upper_Bound(rc);
    }
}

void Build(int x, int l, int r){
    dd[x] = 0; if (l == r) mx[x] = ss[x] = mex1[l];
    else Build(lc), Build(rc), Update(x);
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (RD(n)){

        REP_1_C(i, n)  checkMin(RD(A[i]), 200001);

        int mex = 0; RST(C); REP_1(i, n){
            ++C[A[i]]; while (C[mex]) ++mex;
            mex1[i] = mex;
        }

        fill(C, C+N, n+1); DWN_1(i, n, 1){
            nxt[i] = C[A[i]];
            C[A[i]] = i;
        }

        LL res = 0; Build(root); REP_1(i, n){
            res += ss[1]; if (mx[1] > A[i]){
                c = A[i], a = Upper_Bound(root), b = nxt[i]-1; if (a <= b) Insert(root);
            }
            a = i, b = i, c = 0, Insert(root);
            if (!mx[1]) break;
        }

        OT(res);
    }
}

External link:

https://gist.github.com/lychees/6574078

Posted by xiaodao
Category: HDU