跳转至

二維莫隊

二維莫隊，顧名思義就是每個狀態有四個方向可以擴展。

二維莫隊每次移動指針要操作一行或者一列的數，具體實現方式與普通的一維莫隊類似，這裏不再贅述。這裏重點講塊長選定部分。

塊長選定

記詢問次數為 \(q\)，當前矩陣的左上角座標為 \((x_1,\ y_1)\)，右下角座標為 \((x_2,\ y_2)\)，取塊長為 \(B\)。

那麼指針 \(x_1\) 移動了 \(\Theta(q\cdot B)\) 次，而指針 \(y_2\) 移動了 \(\Theta(n^4\cdot B^{-3})\) 次。

所以只需令 \(q\cdot B=n^4\cdot B^{-3}\)，即 \(B=n\cdot q^{-\frac 14}\) 即可。

注意這樣計算 \(B\) 的結果 可能為 \(0\)，注意特判。

最終，計算部分時間複雜度是 \(\Theta(n^2\cdot q^{\frac 34})\)，加上對詢問的排序過程，總時間複雜度為 \(\Theta(n^2\cdot q^{\frac 34}+q\log q)\)。

例題 1

BZOJ 2639 矩形計算

輸入一個 \(n\times m\) 的矩陣，矩陣的每一個元素都是一個整數，然後有 \(q\) 個詢問，每次詢問一個子矩陣的權值。矩陣的權值是這樣定義的，對於一個整數 \(x\)，如果它在該矩陣中出現了 \(p\) 次，那麼它給該矩陣的權值就貢獻 \(p^2\)。

數據範圍：\(1\leq n,\ m\leq 200\)，\(0\leq q\leq 10^5\)，\(|\) 矩陣元素大小 \(| \leq 2\times 10^9\)。

解題思路

先離散化，二維莫隊時用一個數組記錄每個數當前出現的次數即可。

示例代碼 
 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
#include <bits/stdc++.h>
using namespace std;

int n, m, q, a[201][201];
long long ans[100001];
int disc[250001], cntdisc;  // 离散化用

int blocklen, counts[40001];
long long now;

struct Question {
  int x1, y1, x2, y2, qid;

  bool operator<(Question tmp) const {
    if (x1 / blocklen != tmp.x1 / blocklen) return x1 < tmp.x1;
    if (y1 / blocklen != tmp.y1 / blocklen) return y1 < tmp.y1;
    if (x2 / blocklen != tmp.x2 / blocklen) return x2 < tmp.x2;
    return y2 < tmp.y2;
  }
} Q[100001];

int Qcnt;

void mo_algo_row(int id, int val, int Y1, int Y2) {
  for (int i = Y1; i <= Y2; i++)
    now -= (long long)counts[a[id][i]] * counts[a[id][i]],
        counts[a[id][i]] += val,
        now += (long long)counts[a[id][i]] * counts[a[id][i]];
}

void mo_algo_column(int id, int val, int X1, int X2) {
  for (int i = X1; i <= X2; i++)
    now -= (long long)counts[a[i][id]] * counts[a[i][id]],
        counts[a[i][id]] += val,
        now += (long long)counts[a[i][id]] * counts[a[i][id]];
}

void mo_algo() {
  blocklen = pow(n * m, 0.5) / pow(q, 0.25);
  if (blocklen < 1) blocklen = 1;
  sort(Q + 1, Q + 1 + Qcnt);

  int X1 = 1, Y1 = 1, X2 = 0, Y2 = 0;
  for (int i = 1; i <= Qcnt; i++) {
    while (X1 > Q[i].x1) mo_algo_row(--X1, 1, Y1, Y2);
    while (X2 < Q[i].x2) mo_algo_row(++X2, 1, Y1, Y2);
    while (Y1 > Q[i].y1) mo_algo_column(--Y1, 1, X1, X2);
    while (Y2 < Q[i].y2) mo_algo_column(++Y2, 1, X1, X2);
    while (X1 < Q[i].x1) mo_algo_row(X1++, -1, Y1, Y2);
    while (X2 > Q[i].x2) mo_algo_row(X2--, -1, Y1, Y2);
    while (Y1 < Q[i].y1) mo_algo_column(Y1++, -1, X1, X2);
    while (Y2 > Q[i].y2) mo_algo_column(Y2--, -1, X1, X2);
    ans[Q[i].qid] = now;
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      scanf("%d", a[i] + j), disc[++cntdisc] = a[i][j];
  sort(disc + 1, disc + 1 + cntdisc);
  cntdisc = unique(disc + 1, disc + cntdisc + 1) - disc - 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      a[i][j] = lower_bound(disc + 1, disc + 1 + cntdisc, a[i][j]) - disc;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    Q[++Qcnt] = {x1, y1, x2, y2, i};
  }

  mo_algo();
  for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
  return 0;
}

例題 2

洛谷 P1527 [國家集訓隊] 矩陣乘法

給你一個 \(n\times n\) 的矩陣，\(q\) 次詢問，每次詢問一個子矩形的第 \(k\) 小數。

數據範圍：\(1\leq n\leq 500\)，\(1\leq q\leq 6\times 10^4\)，\(0\leq a_{i,j}\leq 10^9\)。

首先和上一題一樣，需要離散化整個矩陣。但是需要注意，本題除了需要對數值進行分塊，還需要對數值的值域進行分塊，才能求出答案。

這裏還需要用到奇偶化排序進行優化，具體內容請見 普通莫隊算法。

對於本題而言，時間限制不那麼寬，注意代碼常數的處理。取的塊長計算值普遍較小，\(n,\ q\) 都取最大值時塊長大約在 \(11\) 左右，可以直接設定為常數來節約代碼耗時。

示例代碼 
  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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;

void read(int& a) {
  a = 0;
  char c;
  while ((c = getchar()) < 48)
    ;
  do a = (a << 3) + (a << 1) + (c ^ 48);
  while ((c = getchar()) > 47);
}

void write(int x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}

int n, q, a[501][501], ans[60001];
int disc[250001], cntdisc;  // 离散化用
int nn;

int blockId[501], blocklen;               // 分块
int rangeblockId[250001], rangeblocklen;  // 值域分块
int counts[250001], countsum[501];        // 该值次数及值域块总和

struct Position {
  int x, y;
};

vector<Position> pos[250001];

struct Question {
  int x1, y1, x2, y2, k, qid;

  bool operator<(Question tmp) const {
    if (blockId[x1] != blockId[tmp.x1]) return blockId[x1] < blockId[tmp.x1];
    if (blockId[y1] != blockId[tmp.y1])
      return blockId[x1] & 1 ? y1 < tmp.y1 : y1 > tmp.y1;
    if (blockId[y2] != blockId[tmp.y2])
      return blockId[y1] & 1 ? y2 < tmp.y2 : y2 > tmp.y2;
    else
      return blockId[y2] & 1 ? x2 < tmp.x2 : x2 > tmp.x2;
  }
} Q[60001];

int Qcnt;

void mo_algo() {
  blocklen = 11;
  for (int i = 1; i <= n; ++i) blockId[i] = (i - 1) / blocklen + 1;
  rangeblocklen = n + 1;
  for (int i = 1; i <= nn; ++i) rangeblockId[i] = (i - 1) / rangeblocklen + 1;
  counts[a[1][1]] = countsum[rangeblockId[a[1][1]]] = 1;
  sort(Q + 1, Q + 1 + Qcnt);

  int L = 1, R = 1, D = 1, U = 1;
  for (int i = 1; i <= q; ++i) {
    while (R < Q[i].y2) {
      ++R;
      for (int i = U; i <= D; ++i)
        ++counts[a[i][R]], ++countsum[rangeblockId[a[i][R]]];
    }
    while (L > Q[i].y1) {
      --L;
      for (int i = U; i <= D; ++i)
        ++counts[a[i][L]], ++countsum[rangeblockId[a[i][L]]];
    }
    while (D < Q[i].x2) {
      ++D;
      for (int i = L; i <= R; ++i)
        ++counts[a[D][i]], ++countsum[rangeblockId[a[D][i]]];
    }
    while (U > Q[i].x1) {
      --U;
      for (int i = L; i <= R; ++i)
        ++counts[a[U][i]], ++countsum[rangeblockId[a[U][i]]];
    }
    while (R > Q[i].y2) {
      for (int i = U; i <= D; ++i)
        --counts[a[i][R]], --countsum[rangeblockId[a[i][R]]];
      --R;
    }
    while (L < Q[i].y1) {
      for (int i = U; i <= D; ++i)
        --counts[a[i][L]], --countsum[rangeblockId[a[i][L]]];
      ++L;
    }
    while (D > Q[i].x2) {
      for (int i = L; i <= R; ++i)
        --counts[a[D][i]], --countsum[rangeblockId[a[D][i]]];
      --D;
    }
    while (U < Q[i].x1) {
      for (int i = L; i <= R; ++i)
        --counts[a[U][i]], --countsum[rangeblockId[a[U][i]]];
      ++U;
    }
    int res = 1, cnt = 0;
    while (cnt + countsum[res] < Q[i].k && res <= rangeblockId[nn])
      cnt += countsum[res], ++res;
    res = (res - 1) * rangeblocklen + 1;
    while (cnt + counts[res] < Q[i].k && res <= nn) cnt += counts[res], ++res;
    ans[Q[i].qid] = disc[res];
  }
}

int main() {
  read(n);
  read(q);
  nn = n * n;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      int x;
      read(x);
      a[i][j] = disc[++cntdisc] = x;
    }
  sort(disc + 1, disc + 1 + cntdisc);
  cntdisc = unique(disc + 1, disc + cntdisc + 1) - disc - 1;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      a[i][j] = lower_bound(disc + 1, disc + 1 + cntdisc, a[i][j]) - disc;
  for (int i = 1; i <= q; ++i) {
    int x1, y1, x2, y2, k;
    read(x1);
    read(y1);
    read(x2);
    read(y2);
    read(k);
    Q[++Qcnt] = {x1, y1, x2, y2, k, i};
  }

  mo_algo();
  for (int i = 1; i <= q; ++i) write(ans[i]), puts("");
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用