CF121E Lucky Array

思路

正解是线段树？然而我太菜了不会啊。。。

题目的数据范围是 \(10 ^ 5\)，于是我们可以从分块的角度去思考这个问题。

打个表可以发现在题目给定的值域（\(10 ^ 4\)）内满足条件的数一共只有三十个，于是这道题就简单了。先把数列分个块，然后对于每一块，维护一个区间加的标记和一个值域的标记，表示该块内每个数字的个数。对于区间加的操作，对散块就直接暴力累加，对整块就维护标记。对于查询的操作，对散块就暴力的验证其是否符合要求，而对整块就查询块内这三十个数的个数即可，还有就是记得查询时带上区间加的标记。

时间复杂度为 \(O(30 n \sqrt n)\)，空间复杂度的话，由于对每一块都开了一个值域数组，所以是 \(O(10 ^ 4 \sqrt n)\)。

代码

#include <bits/stdc++.h>

using i64 = long long;

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::unordered_set<int> encode;
  std::vector<int> decode;
  [&]() {
    for (int i = 1; i <= 10000; i++) {
      auto check = [](int num) -> bool {
        while (num) {
          if (num % 10 != 4 && num % 10 != 7) { return false; }
          num /= 10;
        }
        return true;
      };
      if (check(i)) { encode.insert(i), decode.push_back(i); }
    }
  }();

  int n, m;
  std::cin >> n >> m;

  int blk = std::sqrt(n + 0.5), cnt = n / blk + !!(n % blk);
  std::vector<int> st(cnt), ed(cnt), bln(n);
  for (int i = 0; i < cnt; i++) { st[i] = i * blk, ed[i] = (i + 1) * blk - 1; }
  ed[cnt - 1] = n - 1;
  for (int i = 0; i < n; i++) { bln[i] = i / blk; }

  std::vector<int> a(n);
  for (int i = 0; i < n; i++) { std::cin >> a[i]; }

  std::vector<std::vector<int>> f(cnt, std::vector<int>(1e4 + 1));
  std::vector<int> add(cnt);
  for (int i = 0; i < n; i++) { f[bln[i]][a[i]]++; }

  while (m--) {
    std::string opt;
    int l, r;
    std::cin >> opt >> l >> r;
    l--, r--;
    if (opt == "add") {
      int val;
      std::cin >> val;
      if (bln[l] == bln[r]) {
        for (int i = l; i <= r; i++) {
          f[bln[l]][a[i]]--, a[i] += val, f[bln[l]][a[i]]++;
        }
      } else {
        for (int i = l; i <= ed[bln[l]]; i++) {
          f[bln[l]][a[i]]--, a[i] += val, f[bln[l]][a[i]]++;
        }
        for (int i = st[bln[r]]; i <= r; i++) {
          f[bln[r]][a[i]]--, a[i] += val, f[bln[r]][a[i]]++;
        }
        for (int i = bln[l] + 1; i < bln[r]; i++) { add[i] += val; }
      }
    } else {
      int ans = 0;
      if (bln[l] == bln[r]) {
        for (int i = l; i <= r; i++) {
          if (encode.count(a[i] + add[bln[l]])) { ans++; }
        }
      } else {
        for (int i = l; i <= ed[bln[l]]; i++) {
          if (encode.count(a[i] + add[bln[l]])) { ans++; }
        }
        for (int i = st[bln[r]]; i <= r; i++) {
          if (encode.count(a[i] + add[bln[r]])) { ans++; }
        }
        for (int i = bln[l] + 1; i < bln[r]; i++) {
          for (auto j : decode) { 
            if (j < add[i]) { continue; }
            ans += f[i][j - add[i]]; 
          }
        }
      }
      std::cout << ans << "\n";
    }
  }

  return 0;
}