hoj-4747 Mex

发表于 分类于 阅读次数： Waline： 本文字数： 854 阅读时长 ≈ 3 分钟

考点

  • 线段树

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 50;
#define lc p << 1
#define rc p << 1 | 1
ll n, a[maxn], mex[maxn], v[maxn], nxt[maxn], tmp[maxn];
// 线段树
// mx：区间最大值
// s：区间和
// tag：覆盖懒标签
ll mx[maxn << 2], s[maxn << 2], tag[maxn << 2];

void up(ll p) {
  s[p] = s[lc] + s[rc];
  mx[p] = max(mx[lc], mx[rc]);
}

void f(ll p, ll l, ll r, ll v) {
  mx[p] = v;
  s[p] = v * (r - l + 1);
}

void down(ll p, ll l, ll r) {
  if (~tag[p]) {
    ll mid = (l + r) >> 1;
    f(lc, l, mid, tag[p]), f(rc, mid + 1, r, tag[p]);
    tag[lc] = tag[rc] = tag[p];
    tag[p] = -1;
  }
}

void build(ll p, ll l, ll r) {
  tag[p] = -1;
  if (l == r) {
    mx[p] = s[p] = mex[l];
    return;
  }
  ll mid = (l + r) >> 1;
  build(lc, l, mid), build(rc, mid + 1, r);
  up(p);
}

void update(ll p, ll l, ll r, ll L, ll R, ll v) {
  if (L <= l && r <= R) {
    f(p, l, r, v);
    tag[p] = v;
    return;
  }
  down(p, l, r);
  ll mid = (l + r) >> 1;
  if (L <= mid) update(lc, l, mid, L, R, v);
  if (R > mid) update(rc, mid + 1, r, L, R, v);
  up(p);
}

// 二分搜索
ll bis(ll p, ll l, ll r, ll v) {
  if (l == r) return mx[p] > v ? l : -1;
  down(p, l, r);
  ll mid = (l + r) >> 1, ans = -1;
  if (mx[lc] > v) ans = bis(lc, l, mid, v);
  if (~ans) return ans;
  return bis(rc, mid + 1, r, v);
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  while (cin >> n && n) {
    memset(v, 0, sizeof(v));
    // 求出区间{1, j}的mex[j]，其中j∈{1, n}
    ll m = 0;
    for (ll i = 1; i <= n; ++i) {
      cin >> a[i];
      // 每个区间的mex不可能大于长度，所以大于长度的没必要计数
      if (a[i] <= n) v[a[i]] = 1;
      while (v[m]) ++m;
      mex[i] = m;
    }
    for (ll i = 0; i <= n; ++i) tmp[i] = n + 1;
    // nxt[x]，记录x右边第一个等于x的下标
    for (ll i = n; i >= 1; --i) {
      // 同上，不需要记录非法值
      if (a[i] > n) continue;
      nxt[i] = tmp[a[i]];
      tmp[a[i]] = i;
    }
    build(1, 1, n);
    ll ans = 0;
    for (ll i = 1; i <= n; ++i) {
      ans += s[1];
      update(1, 1, n, i, i, 0);
      ll l = bis(1, 1, n, a[i]);
      if (l == -1) continue;
      ll r = nxt[i] - 1;
      update(1, 1, n, l, r, a[i]);
    }
    cout << ans << endl;
  }
  return 0;
}

思路

求mex(1, j), 其中j∈{1, n}可以发现，固定左端点时，右端点向右走，mex的值是单调不减的。

mex(2, i)只比mex(1, i)少了a[1]，我们看一下a[1]对结果的影响：

根据上图可以看见，从左端点开始，所有大于a[1]的mex值都会变成a[1]，遇到下一个a[1]停止。

由于左端点固定时，右端点向右是单调不减的，我们需要通过二分找到大于a[1]的mex值里，数组下标最小的，也就是满足条件时一直向左边界靠拢；同时还有区间覆盖，考虑线段树即可。

初始时，我们把mex(1, i)保存到数组mex[i]当中去，线段树的叶子节点初始值就设定为数组mex[i]，有区间求和操作s还有区间最大值操作mx，此时以1为左端点的所有子区间mex值之和就等于s[1]。

在线段树中清除a[1]后，用线段树二分找到大于a[1]的mex值里数组下标最小的，记下标为l；

然后找到数组右边第一个等于a[1]的位置r，随后用线段树把(l, r - 1)这部分的mex值设为a[1]即可，此时就得到了以2为左端点的所有子区间mex值之和s[1]。