跳转至

莫隊配合 bitset

bitset 常用於常規數據結構難以維護的的判定、統計問題，而莫隊可以維護常規數據結構難以維護的區間信息。把兩者結合起來使用可以同時利用兩者的優勢。

例題 「Ynoi2016」掉進兔子洞

本題剛好符合上面提到的莫隊配合 bitset 的特徵。不難想到我們可以分別用 bitset 存儲每一個區間內的出現過的所有權值，一組詢問的答案即所有區間的長度和減去三者的並集元素個數 \(\times 3\)。

但是在莫隊中使用 bitset 也需要針對 bitset 的特性調整算法：

  1. bitset 不能很好地處理同時出現多個權值的情況。我們可以把當前元素離散化後的權值與當前區間的的出現次數之和作為往 bitset 中插入的對象。
  2. 我們平常使用莫隊時，可能會不注意 4 種移動指針的方法順序，所以指針移動的過程中可能會出現區間的左端點在右端點右邊，區間長度為負值的情況，導致元素的個數為負數。這在其他情況下並沒有什麼影響，但是本題中在 bitset 中插入的元素與元素個數有關，所以我們需要注意 4 種移動指針的方法順序，將左右指針分別往左邊和右邊移動的語句寫在前面，避免往 bitset 中插入負數。
  3. 雖然 bitset 用空間小，但是仍然難以承受 \(10 ^ 5 \times 10 ^ 5\) 的數據規模。所以我們需要將詢問劃分成常數塊分別處理，保證空間剛好足夠的情況下時間複雜度不變。
參考代碼 
 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
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100005, M = N / 3 + 10;
int n, m, maxn;
int a[N], ans[M], cnt[N];
bitset<N> sum[M], now;

struct query {
  int l, r, id;

  bool operator<(const query& x) const {
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} q[M * 3];

void static_set() {
  static int tmp[N];
  memcpy(tmp, a, sizeof(a));
  sort(tmp + 1, tmp + n + 1);
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(tmp + 1, tmp + n + 1, a[i]) - tmp;
}

void add(int x) {
  now.set(x + cnt[x]);
  cnt[x]++;
}

void del(int x) {
  cnt[x]--;
  now.reset(x + cnt[x]);
}

void solve() {
  int cnt = 0, tot = 0;
  now.reset();
  for (tot = 0; tot < M - 5 && m; tot++) {
    m--;
    ans[tot] = 0;
    sum[tot].set();
    for (int j = 0; j < 3; j++) {
      scanf("%d%d", &q[cnt].l, &q[cnt].r);
      q[cnt].id = tot;
      ans[tot] += q[cnt].r - q[cnt].l + 1;
      cnt++;
    }
  }
  sort(q, q + cnt);
  for (int i = 0, l = 1, r = 0; i < cnt; i++) {
    while (l > q[i].l) add(a[--l]);
    while (r < q[i].r) add(a[++r]);
    while (l < q[i].l) del(a[l++]);
    while (r > q[i].r) del(a[r--]);
    sum[q[i].id] &= now;
  }
  for (int i = 0; i < tot; i++)
    printf("%d\n", ans[i] - (int)sum[i].count() * 3);
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  static_set();
  maxn = sqrt(n);
  solve();
  memset(cnt, 0, sizeof(cnt));
  solve();
  memset(cnt, 0, sizeof(cnt));
  solve();
  return 0;
}

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, Backl1ght, countercurrent-time, Ir1d, greyqz, MicDZ, ouuan
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用