跳转至

帶修改莫隊

請確保您已經會普通莫隊算法了。如果您還不會，請先閲讀前面的 普通莫隊算法。

特點

普通莫隊是不能帶修改的。

我們可以強行讓它可以修改，就像 DP 一樣，可以強行加上一維 時間維, 表示這次操作的時間。

時間維表示經歷的修改次數。

即把詢問 \([l,r]\) 變成 \([l,r,\text{time}]\)。

那麼我們的座標也可以在時間維上移動，即 \([l,r,\text{time}]\) 多了一維可以移動的方向，可以變成：

  • \([l-1,r,\text{time}]\)
  • \([l+1,r,\text{time}]\)
  • \([l,r-1,\text{time}]\)
  • \([l,r+1,\text{time}]\)
  • \([l,r,\text{time}-1]\)
  • \([l,r,\text{time}+1]\)

這樣的轉移也是 \(O(1)\) 的，但是我們排序又多了一個關鍵字，再搞搞就行了。

可以用和普通莫隊類似的方法排序轉移，做到 \(O(n^{5/3})\)。

這一次我們排序的方式是以 \(n^{2/3}\) 為一塊，分成了 \(n^{1/3}\) 塊，第一關鍵字是左端點所在塊，第二關鍵字是右端點所在塊，第三關鍵字是時間。

最優塊長以及時間複雜度分析

我們設序列長為 \(n\)，\(m\) 個詢問，\(t\) 個修改。

帶修莫隊排序的第二關鍵字是右端點所在塊編號，不同於普通莫隊。

想一想，如果不把右端點分塊：

  • 亂序的右端點對於每個詢問會移動 \(n\) 次。
  • 有序的右端點會帶來亂序的時間，每次詢問會移動 \(t\) 次。

無論哪一種情況，帶來的時間開銷都無法接受。

接下來分析時間複雜度。

設塊長為 \(s\)，則有 \(\dfrac{n}{s}\) 個塊。對於塊 \(i\) 和塊 \(j\)，記有 \(q_{i,j}\) 個詢問的左端點位於塊 \(i\)，右端點位於塊 \(j\)。

每「組」左右端點不換塊的詢問 \((i,j)\)，端點每次移動 \(O(s)\) 次，時間單調遞增，\(O(t)\)。

左右端點換塊的時間忽略不計。

表示一下就是：

\[ \begin{aligned} &\sum_{i=1}^{n/s}\sum_{j=i+1}^{n/s}(q_{i,j}\cdot s+t)\\ =&ms+\left(\dfrac{n}{s}\right)^2t\\ =&ms+\dfrac{n^2t}{s^2} \end{aligned} \]

考慮求導求此式極小值。設 \(f(s)=ms+\dfrac{n^2t}{s^2}\)。那 \(f'(s)=m-\dfrac{2n^2t}{s^3}=0\)。

得 \(s=\sqrt[3]{\dfrac{2n^2t}{m}}=\dfrac{2^{1/3}n^{2/3}t^{1/3}}{m^{1/3}}=s_0\)。

也就是當塊長取 \(\dfrac{n^{2/3}t^{1/3}}{m^{1/3}}\) 時有最優時間複雜度 \(O\left(n^{2/3}m^{2/3}t^{1/3}\right)\)。

常説的 \(O\left(n^{5/3}\right)\) 便是把 \(n,m,t\) 當做同數量級的時間複雜度。

實際操作中還是推薦設定 \(n^{2/3}\) 為塊長。

例題

例題 「國家集訓隊」數顏色/維護隊列

題目大意：給你一個序列，M 個操作，有兩種操作：

  1. 修改序列上某一位的數字
  2. 詢問區間 \([l,r]\) 中數字的種類數（多個相同的數字只算一個）

我們不難發現，如果不帶操作 1（修改）的話，我們就能輕鬆用普通莫隊解決。

但是題目還帶單點修改，所以用 帶修改的莫隊。

過程

先考慮普通莫隊的做法：

  • 每次擴大區間時，每加入一個數字，則統計它已經出現的次數，如果加入前這種數字出現次數為 \(0\)，則説明這是一種新的數字，答案 \(+1\)。然後這種數字的出現次數 \(+1\)。
  • 每次減小區間時，每刪除一個數字，則統計它刪除後的出現次數，如果刪除後這種數字出現次數為 \(0\)，則説明這種數字已經從當前的區間內刪光了，也就是當前區間減少了一種顏色，答案 \(-1\)。然後這種數字的出現次數 \(-1\)。

現在再來考慮修改：

  • 單點修改，把某一位的數字修改掉。假如我們是從一個經歷修改次數為 \(i\) 的詢問轉移到一個經歷修改次數為 \(j\) 的詢問上，且 \(i<j\) 的話，我們就需要把第 \(i+1\) 個到第 \(j\) 個修改強行加上。
  • 假如 \(j<i\) 的話，則需要把第 \(i\) 個到第 \(j+1\) 個修改強行還原。

怎麼強行加上一個修改呢？假設一個修改是修改第 \(pos\) 個位置上的顏色，原本 \(pos\) 上的顏色為 \(a\)，修改後顏色為 \(b\)，還假設當前莫隊的區間擴展到了 \([l,r]\)。

  • 加上這個修改：我們首先判斷 \(pos\) 是否在區間 \([l,r]\) 內。如果是的話，我們等於是從區間中刪掉顏色 \(a\)，加上顏色 \(b\)，並且當前顏色序列的第 \(pos\) 項的顏色改成 \(b\)。如果不在區間 \([l,r]\) 內的話，我們就直接修改當前顏色序列的第 \(pos\) 項為 \(b\)。
  • 還原這個修改：等於加上一個修改第 \(pos\) 項、把顏色 \(b\) 改成顏色 \(a\) 的修改。

因此這道題就這樣用帶修改莫隊輕鬆解決啦！

實現

參考代碼 
  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
102
103
104
#include <algorithm>
#include <cmath>
#include <iostream>

#define int long long
#define endl '\n'

using namespace std;

int qsize;

struct query {
  int id, t, l, r;

  inline bool operator<(query b) {
    if (l / qsize != b.l / qsize) {
      return l / qsize > b.l / qsize;
    } else if (r / qsize != b.r / qsize) {
      return r / qsize > b.r / qsize;
    } else {
      return t > b.t;
    }
  }
} q[150009];

struct operation {
  int p, x;
} r[150009];

char op;
int n, m, x, y, cur, qcnt, rcnt, mp[1500009], a[150009], ans[150009];

inline void add(int x) {
  if (!mp[x]) {
    cur += 1;
  }
  mp[x] += 1;
}

inline void del(int x) {
  mp[x] -= 1;
  if (!mp[x]) {
    cur -= 1;
  }
}

inline void process() {
  sort(q + 1, q + qcnt + 1);
  int L = 1, R = 0, last = 0;
  for (int i = 1; i <= qcnt; i++) {
    while (R < q[i].r) {
      add(a[++R]);
    }
    while (R > q[i].r) {
      del(a[R--]);
    }
    while (L > q[i].l) {
      add(a[--L]);
    }
    while (L < q[i].l) {
      del(a[L++]);
    }
    while (last < q[i].t) {
      last += 1;
      if (r[last].p >= L && r[last].p <= R) {
        add(r[last].x);
        del(a[r[last].p]);
      }
      swap(a[r[last].p], r[last].x);
    }
    while (last > q[i].t) {
      if (r[last].p >= L && r[last].p <= R) {
        add(r[last].x);
        del(a[r[last].p]);
      }
      swap(a[r[last].p], r[last].x);
      last -= 1;
    }
    ans[q[i].id] = cur;
  }
}

signed main() {
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  qsize = pow(n, 2.0 / 3.0);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> op >> x >> y;
    if (op == 'Q') {
      q[++qcnt] = {qcnt, rcnt, x, y};
    } else if (op == 'R') {
      r[++rcnt] = {x, y};
    }
  }
  process();
  for (int i = 1; i <= qcnt; i++) {
    cout << ans[i] << endl;
  }
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, Backl1ght, countercurrent-time, Ir1d, greyqz, MicDZ, ouuan, renbaoshuo, Lixuannan
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用