hdu - 4747

Posted by WildCow on July 13, 2018

Mex

Time Limit: 5000/15000 MS (Java/Others)
Memory Limit: 65535/65535 K (Java/Others)

Description

Mex is a function on a set of integers, which is universally used for impartial game theorem. For a non-negative integer set $S$, $mex(S)$ is defined as the least non-negative integer which is not appeared in S. Now our problem is about mex function on a sequence.

Consider a sequence of non-negative integers {$ai$}, we define $mex(L,R)$ as the least non-negative integer which is not appeared in the continuous subsequence from $aL$ to $aR$, inclusive. Now we want to calculate the sum of $mex(L,R)$ for all $1 <= L <= R <= n$.

Input

The input contains at most 20 test cases. For each test case, the first line contains one integer n, denoting the length of sequence. The next line contains n non-integers separated by space, denoting the sequence. $(1 <= n <= 200000, 0 <= ai <= 10^9)$ The input ends with $n = 0$.

Output

For each test case, output one line containing a integer denoting the answer.

Sample Input

3
0 1 3
5
1 0 2 0 1
0

Sample Output

5
24


区间 $mex$ 的定义不想解释
这道题写的时候感觉特别难受
和其它无数题一样
写完后也觉得
就那样
这题莫名的调了很久qwq

首先这个题的数据是一个假数据
对于 $a_i > n$ 那么肯定不会对区间的 mex 做贡献
所以我们是可以开一个数组计数的

我们考虑用 {$l, r$} 表示区间 [l, r] 的 mex
用 {$l$} 表示 $\sum_{i = l}^{n}${$l,i$} 我就不用汉字说这是什么意思你有本事来打我啊
一个很重要的结论是:存在 $b > a$ 时,有{$l, b$}$\geq${$l, a$}
换一句话说
当我们固定 $l$ 的时候
区间的 mex 会随着 $r$ 的增大不严格递增
简单反证一下就好了
这样就有一个思路
我们先求出所有以第一个位置的点为左端的的区间的 mex

我们先遍历数组
遍历的过程中我们开一个 $cnt$ 数组计数
同时用一个指针 $top$ 初始指向 $cnt$ 中 $0$ 位置
对于遍历到 $a_i$ 时
如果此时指针 $cnt[top]$ 为 0
那么{$1,i$} 的答案就是 $top$
否则就 for 循环把 $top$ 往后挪直到 $cnt[top]$ 为 0
用数组存一下就好了
这样能在 $O(n)$ 的复杂度内处理完

接着我们考虑如何从 {$l$} 推到 {$l + 1$},即尝试去更新这个数组
根据之前说的单调性分三种情况考虑

  • 如果有 {$l, a$} $<$ $l$,那么显然 {$l, a$} $=$ {$l + 1, a$},更一般的,根据单调性对于 {$l, b$} $=$ $l$,我们有 {$l, l…b$} $=$ {$l+1,l+1…b$}
  • 如果存在 $t > l$ 且 $a_t=a_l$,那么有 {$l, t…n$} $=$ {$l+1,t…n$} 对于每个位置的 $t$ 也可以通过 $O(n)$ 的预处理得到
  • 会发生变化的,就只有 {$l,b…t$},有 {$l+1, b…t$} $=$ $l$

所以我们在处理完 {$1$} 后,可以不断地枚举左端点来计算
假设我们已经知道 {$i$} 了,显然此时对于数组的 $i~n$ 的位置是递增的
我们可以通过二分找出最后一个小于等于 $a_i - 1$ 的位置 $x$
再根据预处理得到 $a_i$ 下一个出现的位置 $y$
显然 {$i+1, x…y$} 应该被更新成 $a_i$
更新完后对 $i$ 到 $n$ 求个和就是 {$i$} 了
所以我们需要一个支持区间赋值,区间求和的玩意
线段树!
之前说的二分在线段树上进行就够了

P.S. 有可能出现区间赋值为 0,所以 lazy 标记初始应该为 -1


#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200020;

struct Three
{
    int l;
    int r;
    int minn;
    int lazy;
    LL sum;
};

Three tree[N * 4];
int n;
int ma[N];
int mb[N];
bool vis[N];
int cnt;
int ne[N];
int last[N];
LL ans;

void Up(int x)
{
    tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
    tree[x].minn = min(tree[x << 1].minn, tree[x << 1 | 1].minn);
}

void Down(int x)
{
    int t;

    t = tree[x].lazy;
    if(t != -1){
        tree[x].lazy = -1;
        tree[x << 1].lazy = t;
        tree[x << 1].minn = t;
        tree[x << 1].sum = t * (tree[x << 1].r - tree[x << 1].l + 1);
        tree[x << 1 | 1].lazy = t;
        tree[x << 1 | 1].minn = t;
        tree[x << 1 | 1].sum = t * (tree[x << 1 | 1].r - tree[x << 1 | 1].l + 1);
    }
}

void Build(int x, int l, int r)
{
    tree[x].l = l;
    tree[x].r = r;
    tree[x].lazy = -1;
    if(l == r){
        tree[x].sum = mb[l];
        tree[x].minn = mb[l];
    }
    else{
        int mid;

        mid = l + ((r - l) >> 1);
        Build(x << 1, l, mid);
        Build(x << 1 | 1, mid + 1, r);
        Up(x);
    }
}


void Update(int x, int l, int r, int v)
{
    int ll;
    int rr;

    if(l > r){
        return ;
    }
    ll = tree[x].l;
    rr = tree[x].r;
    if(ll == l && rr == r){
        tree[x].sum = (rr - ll + 1) * v;
        tree[x].minn = v;
        tree[x].lazy = v;
    }
    else{
        int mid;
    
        mid = ll + ((rr - ll) >> 1);
        Down(x);
        Update(x << 1, l, min(mid, r), v);
        Update(x << 1 | 1, max(mid + 1, l), r, v);
        Up(x);
    }
}

int Quary1(int x, int v)
{
    int ll;
    int rr;

    ll = tree[x].l;
    rr = tree[x].r;
    if(ll == rr){
        return ll;
    }
    else{
        int mid;
        int t;
    
        mid = ll + ((rr - ll) >> 1);
        Down(x);
        if(tree[x << 1 | 1].minn > v){
            t = Quary1(x << 1, v);
        }
        else{
            t = Quary1(x << 1 | 1, v);
        }
    
        Up(x);
    
        return t;
    }
}

LL Quary2(int x, int l, int r)
{
    int ll;
    int rr;

    ll = tree[x].l;
    rr = tree[x].r;
    if(l > r){
        return 0;
    }
    if(ll == l && rr == r){
        return tree[x].sum;
    }
    else{
        int mid;
        LL t;
    
        t = 0;
        mid = ll + ((rr - ll) >> 1);
        Down(x);
        t += Quary2(x << 1, l, min(mid, r));
        t += Quary2(x << 1 | 1, max(mid + 1, l), r);
    
        return t;
    }
}

int main(int argc, char const *argv[])
{
    while(scanf("%d", &n) == 1){
        if(!n){
            break;
        }
        cnt = 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i <= n; i ++){
            last[i] = n + 1;
        }
        for(int i = 1; i <= n; i ++){
            scanf("%d", &ma[i]);
            if(ma[i] > n){
                ma[i] = n;
            }
        }
        for(int i = 1; i <= n; i ++){
            if(!vis[ma[i]]){
                vis[ma[i]] = true;
            }
            while(vis[cnt]){
                cnt ++;
            }
            mb[i] = cnt;
        }
        for(int i = n; i >= 1; i --){
            ne[i] = last[ma[i]];
            last[ma[i]] = i;
        }
        Build(1, 1, n);
        ans = tree[1].sum;
        for(int i = 1; i < n; i ++){
            int t;

            t = Quary1(1, ma[i] - 1);
            Update(1, t + 1, ne[i] - 1, ma[i]);
            ans += Quary2(1, i + 1, n);
        }
        printf("%lld\n", ans);
    }
    
    return 0;
}