元素计数⚓︎

不同元素计数⚓︎

在区间查询中，统计区间内不同元素的核心解决方法是：

在处理区间查询时，按右端点从小到大排序，然后逐步扩展右端点。当发现相同元素时，撤销其上一次出现的位置，从而确保每个元素在当前区间内只被计数一次。

因为是按右端点排序的，所以被撤销的操作不会影响查询结果。

给定一个长度为 $n$ 的序列和 $m$ 个查询，每个查询包含两个整数 $l$ 和 $r$ ，计算子区间 $[l, r]$ 中不同整数的个数。

离线查询可持久化线段树

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

struct BIT {
  explicit BIT(int64_t n) : n(n), tree(n + 1) {}

  void point_add(int64_t x, int64_t delta) {
    for (; x <= n; x += lowbit(x)) { tree[x] += delta; }
  }

  int64_t sum(int64_t x) {
    int64_t ret = 0;
    for (; x > 0; x -= lowbit(x)) { ret += tree[x]; }
    return ret;
  }

  int64_t range_sum(int64_t x, int64_t y) { return sum(y) - sum(x - 1); }

  static int64_t lowbit(int64_t x) { return x & (-x); }

  int64_t n;
  vector<int64_t> tree;  // one-based indexing
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  BIT bit(n);
  vector<int64_t> nums(n + 1);
  for (int i = 1; i <= n; i++) { cin >> nums[i]; }

  vector<int64_t> sorted_nums = nums;
  sort(sorted_nums.begin() + 1, sorted_nums.end());
  auto get_rank = [&](int64_t x) {  // 返回x的排名，排名从1开始
    return lower_bound(sorted_nums.begin() + 1, sorted_nums.end(), x) - sorted_nums.begin();
  };

  bit = BIT(n);
  vector<int64_t> last(n + 1, 0);  // last[i]表示第i个数上次出现的位置

  using TIII = tuple<int64_t, int64_t, int64_t>;  // left, right, id

  int64_t m;
  cin >> m;
  vector<TIII> queries(m);
  for (int64_t i = 0; i < m; i++) {
    int64_t left, right;
    cin >> left >> right;
    queries[i] = make_tuple(left, right, i);
  }
  sort(queries.begin(), queries.end(),
       [](const TIII &a, const TIII &b) { return get<1>(a) < get<1>(b); });

  vector<int64_t> answers(m);
  int i = 1;
  for (auto [left, right, id] : queries) {
    // 处理每个查询
    for (; i <= right; i++) {
      int64_t rank = get_rank(nums[i]);
      // 取消上次出现
      if (last[rank] != 0) { bit.point_add(last[rank], -1); }
      bit.point_add(i, 1);  // 添加本次出现
      last[rank] = i;
    }
    answers[id] = bit.range_sum(left, right);
  }

  for (const auto &ans : answers) { cout << ans << '\n'; }

  return 0;
}

版本

可持久化线段树的版本通过为每个位置创建一个新的版本来记录元素的出现情况。当一个元素再次出现时，更新其上一次出现位置的节点，将该位置的值设为0，从而确保每个元素在当前区间内只被计数一次。

TLE

使用可持久化线段树版本可以实现在线查询，扩展到新的右端点时就创建一个新的版本。然而，这样实现在会 TLE 两个测试点。因此，对于该问题还是使用离线查询。

C++

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

struct node {
  int left;
  int right;
  int size;  // 记录该节点区间内有多少个元素
};

vector<node> nodes;  // 所有节点

struct p_segment_tree {
  p_segment_tree() {
    nodes.clear();               // 清空节点
    nodes.emplace_back(node{});  // 占位, 节点编号从1开始
  }

  // 更新当前节点的出现次数
  static void push_up(int i) {
    nodes[i].size = nodes[nodes[i].left].size + nodes[nodes[i].right].size;
  }

  static int clone(int i) {
    int new_node = nodes.size();   // 新节点编号
    nodes.emplace_back(nodes[i]);  // 克隆当前节点
    return new_node;
  }

  // 修改节点的值, 返回新版本的根节点
  int update(int index, int val, int i, int l, int r) {
    int new_node = clone(i);  // 克隆当前节点
    if (l == r) {
      nodes[new_node].size += val;
      return new_node;
    }
    int mid = l + ((r - l) / 2);
    if (index <= mid) {
      nodes[new_node].left = update(index, val, nodes[i].left, l, mid);
    } else {
      nodes[new_node].right = update(index, val, nodes[i].right, mid + 1, r);
    }
    push_up(new_node);
    return new_node;
  }

  // 查询到左端点ql为止的区间元素个数
  int query(int ql, int root_v, int l, int r) {
    if (l == r) { return nodes[root_v].size; }
    int mid = l + ((r - l) / 2);
    if (ql <= mid) {
      return query(ql, nodes[root_v].left, l, mid) + nodes[nodes[root_v].right].size;
    }
    return query(ql, nodes[root_v].right, mid + 1, r);
  };
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  nodes.reserve(40 * n);  // 预估节点数量，避免多次扩容
  vector<int> nums(n + 1);
  for (int i = 1; i <= n; i++) { cin >> nums[i]; }

  vector<int> sorted_nums = nums;
  sort(sorted_nums.begin() + 1, sorted_nums.end());
  auto get_rank = [&](int x) {  // 返回x的排名，排名从1开始
    return lower_bound(sorted_nums.begin() + 1, sorted_nums.end(), x) - sorted_nums.begin();
  };

  p_segment_tree pst;
  vector<int> roots(n + 1);    // roots[i]表示前i个数对应的线段树根节点
  int v = 0;                   // 当前处理到第v个数, roots[0]表示空树
  vector<int> last(n + 1, 0);  // last[i]表示第i个数上次出现的位置

  int m;
  cin >> m;

  using TIII = tuple<int, int, int>;  // left, right, id
  vector<TIII> queries(m);
  for (int i = 0; i < m; i++) {
    int left, right;
    cin >> left >> right;
    queries[i] = make_tuple(left, right, i);
  }
  sort(queries.begin(), queries.end(),
       [](const TIII &a, const TIII &b) { return get<1>(a) < get<1>(b); });

  vector<int> answers(m);
  for (auto [left, right, id] : queries) {
    while (v < right) {
      ++v;
      int rank         = get_rank(nums[v]);
      int current_root = roots[v - 1];
      // 取消上次出现
      if (last[rank] != 0) { current_root = pst.update(last[rank], -1, current_root, 1, n); }
      current_root = pst.update(v, 1, current_root, 1, n);  // 添加本次出现
      roots[v]     = current_root;
      last[rank]   = v;
    }
    answers[id] = pst.query(left, roots[right], 1, n);
  }

  for (const auto &ans : answers) { cout << ans << '\n'; }

  return 0;
}

频次平衡子数组⚓︎

频次平衡类问题通常涉及寻找一个子区间满足某种计数平衡条件。

对这类问题通常每个位置转化为一个状态，并在前缀状态上使用哈希表寻找匹配的前缀，从而确定满足条件的子区间。

形式化地：

$\text{feature}[i] = f(\text{count}_1(i), \text{count}_2(i), \dots)$

若存在 $l < r$ 使得

$\text{feature}[r] = \text{feature}[l],$

则说明区间 $(l+1, r]$ 是一个平衡区间。

于是只需记录每个状态第一次出现的位置，用于计算最长距离。

连续数组

给定一个二进制数组 $nums$ , 找到含有相同数量的 $0$ 和 $1$ 的最长连续子数组，并返回该子数组的长度。

前缀和

将数组中的 $0$ 替换为 $-1$ ，然后计算前缀和。对于任意两个前缀和相等的位置 $i$ 和 $j$ ，子数组 $nums[i+1 \ldots j]$ 中 $0$ 和 $1$ 的数量相同。通过记录每个前缀和第一次出现的位置，可以在遍历数组时计算出最长的满足条件的子数组长度。

C++

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
 public:
  int findMaxLength(vector<int> &nums) {
    unordered_map<int, int> first;
    first[0]   = -1;  // 前缀和为0时，起点在 -1
    int prefix = 0, res = 0;
    for (int i = 0; i < nums.size(); ++i) {
      prefix += (nums[i] == 1 ? 1 : -1);
      if (first.count(prefix)) {
        res = max(res, i - first[prefix]);
      } else {
        first[prefix] = i;
      }
    }
    return res;
  }
};

每个元音包含偶数次的最长子字符串

给定一个字符串 $s$ ，找到含有每个元音字母（a, e, i, o, u）出现偶数次的最长子字符串，并返回该子字符串的长度。

前缀和

将每个元音字母的出现次数视为一个状态，使用一个整数表示每个状态的奇偶性。通过记录每个状态第一次出现的位置，可以在遍历字符串时计算出最长的满足条件的子字符串长度。

C++

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
 public:
  int findTheLongestSubstring(string s) {
    unordered_map<int, int> first;
    first[0] = -1;
    int mask = 0, res = 0;

    for (int i = 0; i < s.size(); ++i) {
      if (string("aeiou").find(s[i]) != string::npos) { mask ^= 1 << (s[i] - 'a'); }
      if (first.count(mask)) {
        res = max(res, i - first[mask]);
      } else {
        first[mask] = i;
      }
    }
    return res;
  }
};

最长的平衡子串 II

给你一个只包含字符 'a'、'b' 和 'c' 的字符串 $s$ 。如果一个子串中所有不同字符出现的次数都相同，则称该子串为平衡子串。请返回 $s$ 的最长平衡子串的长度。

二维前缀差

分别讨论只有一种字符、两种字符和三种字符的情况。对于两种字符的情况，可以使用类似于连续数组的方法，计算两个字符出现次数的差值，并记录每个差值第一次出现的位置。对于三种字符的情况，可以使用一个二维状态表示三个字符的出现次数差值，并记录每个状态第一次出现的位置。

C++

#include <cstdint>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
 public:
  int longestBalanced(string s) {
    int n   = s.size();
    int res = 0;
    {  // 一种字母相同
      for (int i = 0; i < n;) {
        int start = i;
        for (i++; i < n && s[i] == s[i - 1]; i++);
        res = max(res, i - start);
      }
    }
    {  // 两种字母相同
      auto count = [&](char x, char y) -> void {
        for (int i = 0; i < n; i++) {  // 枚举起点, 跳过不包含 x 和 y 的字符
          unordered_map<int, int> first;
          first[0]   = i - 1;  // 前缀和为0时，起点在 i - 1
          int prefix = 0;      // x 的个数减去 y 的个数
          for (; i < n && (s[i] == x || s[i] == y); i++) {
            prefix += s[i] == x ? 1 : -1;
            if (first.contains(prefix)) {
              res = max(res, i - first[prefix]);
            } else {
              first[prefix] = i;
            }
          }
        }
      };
      count('a', 'b');
      count('a', 'c');
      count('b', 'c');
    }
    {  // 三种字母相同
      unordered_map<int64_t, int> first;
      int64_t cnt0 = 0, cnt1 = 0, cnt2 = 0;

      auto encode
          = [&](int64_t x, int64_t y) -> int64_t { return (x << 32) ^ (y & 0xFF'FF'FF'FF); };

      first[encode(0, 0)] = -1;  // 初始状态

      for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'a') {
          cnt0++;
        } else if (s[i] == 'b') {
          cnt1++;
        } else {
          cnt2++;
        }
        int64_t key = encode(cnt1 - cnt0, cnt2 - cnt0);
        if (first.count(key)) {
          res = max(res, i - first[key]);
        } else {
          first[key] = i;
        }
      }

      return res;
    }
  }
};

最长平衡子数组 II

给你一个整数数组 $nums$ ，如果子数组中不同偶数的数量等于不同奇数的数量，则称该子数组是平衡的。

返回最长平衡子数组的长度。

线段树 + 前缀和

使用线段树维护前缀和信息。遍历数组时，计算当前前缀和，并根据当前元素的奇偶性更新线段树。对于每个前缀和，使用线段树查询最早出现该前缀和的位置，从而计算出最长的平衡子数组长度。

前缀和的定义为：对于位置 $i$ ，若 $nums[i]$ 为偶数，则前缀和加 $1$ ，否则减 $1$ 。这样，前缀和相等的位置表示在该区间内偶数和奇数的数量相等(1)。由于每次更新时只会加减 $1$ ，因此通过维护线段树的最小值和最大值，可以高效地查询前缀和的位置。

注意由于线段树的区间是从1开始的，因此在处理前缀和时需要进行适当的偏移。

如果区间的 $min \leq target \leq max$ ，那必然存在某个位置 $pos$ 等于 $target$ 。这是因为每次更新只会加减 $1$ ，所以区间内的值是连续的。

C++

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
  struct segment_tree {
    vector<int> min;      // 区间最小值
    vector<int> max;      // 区间最大值
    vector<int> tag_add;  // 区间加法懒标记

    explicit segment_tree(int n) : min(n * 4), max(n * 4), tag_add(n * 4) {}

    void push_up(int i) {
      min[i] = std::min(min[2 * i], min[2 * i + 1]);
      max[i] = std::max(max[2 * i], max[2 * i + 1]);
    }

    void lazy_add(int i, int val, int count) {
      tag_add[i] += val;

      min[i]     += val;
      max[i]     += val;
    }

    // 向下传递懒标记
    void push_down(int i, int left_count, int right_count) {
      if (tag_add[i] != 0) {  // 将加法标记传递给子节点
        lazy_add(2 * i, tag_add[i], left_count);
        lazy_add(2 * i + 1, tag_add[i], right_count);
        tag_add[i] = 0;  // 清空根节点加法标记
      }
    }

    // 区间加法: range_add(x, y, val, 1, 1, n) 将区间 [x,y] 的值加上 val
    void range_add(int ql, int qr, int val, int i, int l, int r) {
      if (ql <= l && r <= qr) {  // 区间覆盖, 直接更新
        lazy_add(i, val, r - l + 1);
        return;
      }
      int mid = l + ((r - l) / 2);
      push_down(i, mid - l + 1, r - mid);
      if (ql <= mid) { range_add(ql, qr, val, 2 * i, l, mid); }
      if (qr > mid) { range_add(ql, qr, val, 2 * i + 1, mid + 1, r); }
      push_up(i);
    }

    // 查找区间内第一个等于 target 的位置, 找不到返回 -1
    int find_first(int ql, int qr, int target, int i, int l, int r) {
      if (l > qr || r < ql || target < min[i] || target > max[i]) {  // 无效区间
        return -1;
      }
      if (l == r) {  // 此处必然等于 target
        return l;
      }
      int mid = l + ((r - l) / 2);
      push_down(i, mid - l + 1, r - mid);
      int res = find_first(ql, qr, target, 2 * i, l, mid);
      if (res < 0) {  // 去右子树找
        res = find_first(ql, qr, target, 2 * i + 1, mid + 1, r);
      }
      return res;
    }
  };

 public:
  int longestBalanced(vector<int> &nums) {
    int n = nums.size();
    segment_tree seg_tree(n + 1);  // 前缀和，区间为 [0, n]
    unordered_map<int, int> last;
    int ans = 0, sum = 0;
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      int v = (x % 2 == 0) ? 1 : -1;
      if (!last.contains(x)) {
        sum += v;  // 维护前缀和
        // [i+1, n], 第i+1个位置表示前i个数的前缀和
        seg_tree.range_add(i + 1, n, v, 1, 0, n);
      } else {
        int pre = last[x];  // 上次出现位置
        // 取消上次出现的影响, 上一次x出现的位置影响了区间 [pre+1, n]
        // 当前x的位置影响了区间 [i+1, n]，把[pre+1, i]的值减去v
        seg_tree.range_add(pre + 1, i, -v, 1, 0, n);
      }
      last[x] = i;
      // 查找前缀和等于sum的最左位置, 第i个位置表示前i-1个数的前缀和
      int pos = seg_tree.find_first(0, i, sum, 1, 0, n);
      if (pos >= 0) { ans = std::max(ans, i - pos + 1); }
    }
    return ans;
  }
};

元素计数⚓︎

不同元素计数⚓︎

频次平衡子数组⚓︎

评论