跳转至

分块⚓︎

分块的基本思想是将数据划分为若干个大小相等的块，从而在块内进行操作以提高效率。分块技术常用于处理大规模数据集，尤其是在需要频繁查询和更新的场景中。

一般情况下，分块的大小选择为 \sqrt{n}，这样可以在 O(\sqrt{n}) 的时间复杂度内完成查询和更新操作。总体时间复杂度通常为 O((n + q) \sqrt{n})，其中 n 是数据规模，q 是操作次数。

区间查询⚓︎

分块可以有效地处理区间查询问题。通过将数据划分为若干个块，可以在块内进行快速查询，同时在块之间进行合并操作。查询时对于完全包含的块可以直接使用预处理的信息，而对于部分包含的块则需要逐个处理。

Give Away

给定一个长度为 n 的数组，支持两种操作：

  1. 查询区间 [l, r] 中大于等于 x 的元素个数。
  2. 修改数组中某个位置的元素值。
C++
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;

  vector<int> nums(n + 1);
  for (int i = 1; i <= n; i++) { cin >> nums[i]; }
  vector<int> sorted = nums;
  // 预处理分块信息
  int block_len      = sqrt(n);
  int block_cnt      = (n + block_len - 1) / block_len;
  vector<int> block_id(n + 1);
  vector<int> block_left(block_cnt + 1);
  vector<int> block_right(block_cnt + 1);
  for (int i = 1; i <= n; i++) { block_id[i] = (i - 1) / block_len + 1; }
  // 对每块内的元素进行排序，方便后续查询
  auto *p = sorted.data();
  for (int i = 1; i <= block_cnt; i++) {
    block_left[i]  = (i - 1) * block_len + 1;
    block_right[i] = min(i * block_len, n);
    sort(p + block_left[i], p + block_right[i] + 1);
  }

  auto block_count = [&](int bid, int val) {
    return p + block_right[bid] + 1
         - lower_bound(p + block_left[bid], p + block_right[bid] + 1, val);
  };

  auto query = [&](int l, int r, int val) {
    int cnt      = 0;
    int left_id  = block_id[l];
    int right_id = block_id[r];
    if (left_id == right_id) {  // 同一块内直接计算
      for (int i = l; i <= r; i++) {
        if (nums[i] >= val) { cnt++; }
      }
    } else {
      for (int i = l; i <= block_right[left_id]; i++) {  // 计算左边界块
        if (nums[i] >= val) { cnt++; }
      }
      // 计算中间完整块
      for (int i = left_id + 1; i <= right_id - 1; i++) { cnt += block_count(i, val); }
      for (int i = block_left[right_id]; i <= r; i++) {  // 计算右边界块
        if (nums[i] >= val) { cnt++; }
      }
    }
    return cnt;
  };

  auto update = [&](int i, int v) {
    int b_id  = block_id[i];
    int left  = block_left[b_id];
    int right = block_right[b_id];
    nums[i]   = v;
    copy(nums.data() + left, nums.data() + right + 1, p + left);
    sort(p + left, p + right + 1);
  };

  int m;
  cin >> m;
  for (int _ = 0; _ < m; _++) {
    int op;
    cin >> op;
    if (op == 0) {
      int l, r, val;
      cin >> l >> r >> val;
      cout << query(l, r, val) << "\n";
    } else {
      int i, v;
      cin >> i >> v;
      update(i, v);
    }
  }

  return 0;
}

带修改的区间查询⚓︎

对于需要支持区间修改的查询问题，分块技术同样适用。通过在每个块中维护一个延迟标记，可以在查询时考虑这些修改，从而提高效率。如果修改操作覆盖整个块，可以直接更新块的标记，而无需逐个更新块内的元素。对于部分覆盖的块，则需要逐个更新块内的元素。

教主的魔法

给定一个长度为 n 的数组，支持两种操作：

  1. 查询区间 [l, r] 中大于等于 x 的元素个数。
  2. 将区间 [l, r] 内的所有元素增加一个值 v。
C++
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<int> nums(n + 1);
  for (int i = 1; i <= n; i++) { cin >> nums[i]; }
  vector<int> sorted = nums;
  // 预处理分块信息
  int block_len = sqrt(n);
  int block_cnt = (n + block_len - 1) / block_len;
  vector<int> block_id(n + 1);
  vector<int> block_left(block_cnt + 1);
  vector<int> block_right(block_cnt + 1);
  vector<int> added(block_cnt + 1, 0);  // 用于记录每块的增量
  for (int i = 1; i <= n; i++) { block_id[i] = (i - 1) / block_len + 1; }
  // 对每块内的元素进行排序，方便后续查询
  auto *p = sorted.data();
  for (int i = 1; i <= block_cnt; i++) {
    block_left[i]  = (i - 1) * block_len + 1;
    block_right[i] = min(i * block_len, n);
    sort(p + block_left[i], p + block_right[i] + 1);
  }

  auto block_count = [&](int bid, int val) {
    val -= added[bid];  // 减去当前块的增量
    return p + block_right[bid] + 1
         - lower_bound(p + block_left[bid], p + block_right[bid] + 1, val);
  };

  auto query = [&](int l, int r, int val) {
    int cnt      = 0;
    int left_id  = block_id[l];
    int right_id = block_id[r];
    if (left_id == right_id) {  // 同一块内直接计算
      for (int i = l; i <= r; i++) {
        if (nums[i] + added[left_id] >= val) { cnt++; }
      }
    } else {
      for (int i = l; i <= block_right[left_id]; i++) {  // 计算左边界块
        if (nums[i] + added[left_id] >= val) { cnt++; }
      }
      // 计算中间完整块
      for (int i = left_id + 1; i <= right_id - 1; i++) { cnt += block_count(i, val); }
      for (int i = block_left[right_id]; i <= r; i++) {  // 计算右边界块
        if (nums[i] + added[right_id] >= val) { cnt++; }
      }
    }
    return cnt;
  };
  // 同一块内直接更新
  auto inner_update = [&](int b_id, int l, int r, int val) {
    for (int i = l; i <= r; i++) { nums[i] += val; }
    copy(nums.data() + block_left[b_id], nums.data() + block_right[b_id] + 1, p + block_left[b_id]);
    sort(p + block_left[b_id], p + block_right[b_id] + 1);
  };

  auto update = [&](int l, int r, int val) {
    int left_id  = block_id[l];
    int right_id = block_id[r];
    if (left_id == right_id) {  // 同一块内直接计算
      inner_update(left_id, l, r, val);
    } else {
      inner_update(left_id, l, block_right[left_id], val);  // 更新左边界块
      // 计算中间完整块
      for (int i = left_id + 1; i <= right_id - 1; i++) { added[i] += val; }
      inner_update(right_id, block_left[right_id], r, val);  // 更新右边界块
    }
  };

  for (int _ = 0; _ < m; _++) {
    char op;
    int l, r, val;
    cin >> op >> l >> r >> val;
    if (op == 'A') {
      cout << query(l, r, val) << "\n";
    } else {
      update(l, r, val);
    }
  }

  return 0;
}

块间信息合并⚓︎

在处理区间查询时，可能会遇到需要根据块间信息进行合并的情况，常常需要讨论散块对散块、散块对整块、整块对整块等多种情况。

Yuno loves sqrt technology I

给定一个长度为 n 的数组，支持查询区间 [l, r] 中的逆序对数量。

Hint
  1. 将数组分块，预处理每个块内的逆序对数量，并计算前缀和和后缀和。
  2. 对于查询区间 [l, r]，根据 l 和 r 所在的块进行分类讨论：
    • 如果 l 和 r 在同一块内，直接使用前缀和计算，并减去不合法的逆序对数量。
    • 如果 l 和 r 跨越多个块：包括（1）左边散块和右边散块各自的逆序对数量（2）左边散块与右边散块的逆序对数量（3）左边散块与中间整块的逆序对数量（4）右边散块与中间整块的逆序对数量（5）中间整块之间的逆序对数量。
C++
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iostream>
using namespace std;

struct Node {
  int v, i;

  bool operator<(const Node &other) const { return v != other.v ? v < other.v : i < other.i; }
};

const int MAX_N = 100'001;
const int MAX_B = 701;
// 读取数据
int n, m;
int arr[MAX_N];
Node sorted[MAX_N];
// 分块信息
int blen, bnum;
int bi[MAX_N];
int bl[MAX_B];
int br[MAX_B];
// 树状数组
int tree[MAX_N];
// 预处理信息
int pre[MAX_N];            // 从i所在块左端点到i的逆序对数量
int suf[MAX_N];            // 从i到i所在块右端点的逆序对数量
int cnt[MAX_B][MAX_N];     // cnt[i][v]: 前i块中值小于等于v的元素数量
int64_t dp[MAX_B][MAX_B];  // dp[i][j]: 第i块到第j块的逆序对数量

inline int lowbit(int i) { return i & -i; }

inline void add(int i, int v) {
  while (i <= n) {
    tree[i] += v;
    i       += lowbit(i);
  }
}

inline int sum(int i) {
  int ret = 0;
  while (i > 0) {
    ret += tree[i];
    i   -= lowbit(i);
  }
  return ret;
}

// 计算块x的[xl,xr]和块y的[yl,yr]之间的逆序对数量
inline int count_inversion(int x, int xl, int xr, int y, int yl, int yr) {
  int ans = 0;
  for (int p1 = bl[x], p2 = bl[y], cnt = 0; p1 <= br[x]; p1++) {
    if (xl <= sorted[p1].i && sorted[p1].i <= xr) {
      while (p2 <= br[y] && sorted[p1].v > sorted[p2].v) {
        if (yl <= sorted[p2].i && sorted[p2].i <= yr) { cnt++; }
        p2++;
      }
      ans += cnt;
    }
  }
  return ans;
}

// 计算区间[l,r]的逆序对数量
int64_t query(int l, int r) {
  int64_t ans = 0;
  int lb = bi[l], rb = bi[r];
  if (lb == rb) {
    if (l == bl[lb]) {  // 区间从块左端点开始, 直接使用前缀和
      ans = pre[r];
    } else {  // 否则使用前缀和差分并减去非法部分（[bl, l-1]和[l, r]形成的逆序对数量）
      ans = pre[r] - pre[l - 1] - count_inversion(lb, bl[lb], l - 1, lb, l, r);
    }
    return ans;
  }
  // 跨块区间, 先计算左右散块部分
  ans = suf[l] + pre[r] + count_inversion(lb, l, br[lb], rb, bl[rb], r);
  // 左边散块与中间整块部分
  for (int i = l; i <= br[lb]; i++) { ans += cnt[rb - 1][arr[i]] - cnt[lb][arr[i]]; }
  // 右边散块与中间整块部分
  for (int i = bl[rb]; i <= r; i++) {
    ans += br[rb - 1] - bl[lb + 1] + 1 - (cnt[rb - 1][arr[i]] - cnt[lb][arr[i]]);
  }
  ans += dp[lb + 1][rb - 1]; // 中间整块部分
  return ans;
}

void prepare() {
  blen = static_cast<int>(sqrt(n / 4));
  blen = max(blen, 1);
  bnum = (n + blen - 1) / blen;
  for (int i = 1; i <= n; i++) { bi[i] = (i - 1) / blen + 1; }
  for (int i = 1; i <= bnum; i++) {
    bl[i] = (i - 1) * blen + 1;
    br[i] = min(i * blen, n);
    sort(sorted + bl[i], sorted + br[i] + 1);
  }

  for (int i = 1; i <= bnum; i++) {
    // 计算块内逆序对前缀
    for (int j = bl[i]; j <= br[i]; j++) {
      cnt[i][arr[j]]++;  // 统计前i块中值为arr[j]的元素数量
      if (j != bl[i]) { pre[j] = pre[j - 1] + sum(n) - sum(arr[j]); }
      add(arr[j], 1);
    }
    for (int j = bl[i]; j <= br[i]; j++) { add(arr[j], -1); }
    // 计算块内逆序对后缀
    for (int j = br[i]; j >= bl[i]; j--) {
      if (j != br[i]) { suf[j] = suf[j + 1] + sum(arr[j]); }
      add(arr[j], 1);
    }
    for (int j = bl[i]; j <= br[i]; j++) { add(arr[j], -1); }
    // 计算前i块中值小于等于j的元素数量
    int tmp = 0;
    for (int j = 1; j <= n; j++) {
      tmp       += cnt[i][j];
      cnt[i][j]  = tmp + cnt[i - 1][j];
    }
  }
  for (int l = bnum; l >= 1; l--) {
    dp[l][l] = pre[br[l]];                 // 计算块内逆序对
    for (int r = l + 1; r <= bnum; r++) {  // 计算块间逆序对
      dp[l][r] = dp[l + 1][r] + dp[l][r - 1] - dp[l + 1][r - 1]
               + count_inversion(l, bl[l], br[l], r, bl[r], br[r]);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &arr[i]);
    sorted[i] = {.v = arr[i], .i = i};
  }
  prepare();
  int64_t last_ans = 0;
  for (int i = 1, l, r; i <= m; i++) {
    scanf("%d %d", &l, &r);
    l = l ^ last_ans;
    r = r ^ last_ans;
    // 确保查询区间合法
    l        = max(l, 1);
    r        = min(r, n);
    last_ans = query(l, r);
    printf("%lld\n", last_ans);
  }
  return 0;
}
RE与TLE

使用std::cin和std::cout会RE？尚不清楚原因，改用scanf和printf后通过。

时限为750ms，前三个测评点卡上限通过，大约700ms。

评论