跳转至

回滾莫隊

引入

有些題目在區間轉移時，可能會出現增加或者刪除無法實現的問題。在只有增加不可實現或者只有刪除不可實現的時候，就可以使用回滾莫隊在 \(O(n \sqrt m)\) 的時間內解決問題。回滾莫隊的核心思想就是：既然只能實現一個操作，那麼就只使用一個操作，剩下的交給回滾解決。

回滾莫隊分為只使用增加操作的回滾莫隊和只使用刪除操作的回滾莫隊。以下僅介紹只使用增加操作的回滾莫隊，只使用刪除操作的回滾莫隊和只使用增加操作的回滾莫隊只在算法實現上有一點區別，故不再贅述。

例題 JOISC 2014 Day1 歷史研究

給你一個長度為 \(n\) 的數組 \(A\) 和 \(m\) 個詢問 \((1 \leq n, m \leq 10^5)\)，每次詢問一個區間 \([L, R]\) 內重要度最大的數字，要求 輸出其重要度。一個數字 \(i\) 重要度的定義為 \(i\) 乘上 \(i\) 在區間內出現的次數。

在這個問題中，在增加的過程中更新答案是很好實現的，但是在刪除的過程中更新答案是不好實現的。因為如果增加會影響答案，那麼新答案必定是剛剛增加的數字的重要度，而如果刪除過後區間重要度最大的數字改變，我們很難確定新的重要度最大的數字是哪一個。所以，普通的莫隊很難解決這個問題。

過程

  • 對原序列進行分塊，對詢問按以左端點所屬塊編號升序為第一關鍵字，右端點升序為第二關鍵字的方式排序。
  • 按順序處理詢問：
    • 如果詢問左端點所屬塊 \(B\) 和上一個詢問左端點所屬塊的不同，那麼將莫隊區間的左端點初始化為 \(B\) 的右端點加 \(1\), 將莫隊區間的右端點初始化為 \(B\) 的右端點；
    • 如果詢問的左右端點所屬的塊相同，那麼直接掃描區間回答詢問；
    • 如果詢問的左右端點所屬的塊不同：
      • 如果詢問的右端點大於莫隊區間的右端點，那麼不斷擴展右端點直至莫隊區間的右端點等於詢問的右端點；
      • 不斷擴展莫隊區間的左端點直至莫隊區間的左端點等於詢問的左端點；
      • 回答詢問；
      • 撤銷莫隊區間左端點的改動，使莫隊區間的左端點回滾到 \(B\) 的右端點加 \(1\)。

複雜度證明

假設回滾莫隊的分塊大小是 \(b\)：

  • 對於左、右端點在同一個塊內的詢問，可以在 \(O(b)\) 時間內計算；
  • 對於其他詢問，考慮左端點在相同塊內的詢問，它們的右端點單調遞增，移動右端點的時間複雜度是 \(O(n)\)，而左端點單次詢問的移動不超過 \(b\)，因為有 \(\frac{n}{b}\) 個塊，所以總複雜度是 \(O(mb+\frac{n^2}{b})\)，取 \(b=\frac{n}{\sqrt{m}}\) 最優，時間複雜度為 \(O(n\sqrt{m})\)。

實現

參考代碼 
 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, q;
int x[N], t[N], m;

struct Query {
  int l, r, id;
} Q[N];

int pos[N], L[N], R[N], sz, tot;
int cnt[N], __cnt[N];
ll ans[N];

bool cmp(const Query& A, const Query& B) {
  if (pos[A.l] == pos[B.l]) return A.r < B.r;
  return pos[A.l] < pos[B.l];
}

void build() {
  sz = sqrt(n);
  tot = n / sz;
  for (int i = 1; i <= tot; i++) {
    L[i] = (i - 1) * sz + 1;
    R[i] = i * sz;
  }
  if (R[tot] < n) {
    ++tot;
    L[tot] = R[tot - 1] + 1;
    R[tot] = n;
  }
}

void Add(int v, ll& Ans) {
  ++cnt[v];
  Ans = max(Ans, 1LL * cnt[v] * t[v]);
}

void Del(int v) { --cnt[v]; }

int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &x[i]), t[++m] = x[i];
  for (int i = 1; i <= q; i++) scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;

  build();

  // 对询问进行排序
  for (int i = 1; i <= tot; i++)
    for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
  sort(Q + 1, Q + 1 + q, cmp);

  // 离散化
  sort(t + 1, t + 1 + m);
  m = unique(t + 1, t + 1 + m) - (t + 1);
  for (int i = 1; i <= n; i++) x[i] = lower_bound(t + 1, t + 1 + m, x[i]) - t;

  int l = 1, r = 0, last_block = 0, __l;
  ll Ans = 0, tmp;
  for (int i = 1; i <= q; i++) {
    // 询问的左右端点同属于一个块则暴力扫描回答
    if (pos[Q[i].l] == pos[Q[i].r]) {
      for (int j = Q[i].l; j <= Q[i].r; j++) ++__cnt[x[j]];
      for (int j = Q[i].l; j <= Q[i].r; j++)
        ans[Q[i].id] = max(ans[Q[i].id], 1LL * t[x[j]] * __cnt[x[j]]);
      for (int j = Q[i].l; j <= Q[i].r; j++) --__cnt[x[j]];
      continue;
    }

    // 访问到了新的块则重新初始化莫队区间
    if (pos[Q[i].l] != last_block) {
      while (r > R[pos[Q[i].l]]) Del(x[r]), --r;
      while (l < R[pos[Q[i].l]] + 1) Del(x[l]), ++l;
      Ans = 0;
      last_block = pos[Q[i].l];
    }

    // 扩展右端点
    while (r < Q[i].r) ++r, Add(x[r], Ans);
    __l = l;
    tmp = Ans;

    // 扩展左端点
    while (__l > Q[i].l) --__l, Add(x[__l], tmp);
    ans[Q[i].id] = tmp;

    // 回滚
    while (__l < l) Del(x[__l]), ++__l;
  }
  for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
  return 0;
}

參考資料

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