HDU 4747. Mex

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