题解：P12525 [Aboi Round 1] 私は雨

_Kagamine_Rin_ · 2025-05-21 19:44:37 · 题解

这题真的是毒瘤啊……

注：本题解提供 \mathcal{O}(n\sqrt {n\log n}) 的解法，不是正解，如果要学习 \mathcal{O}(n\sqrt n) 的正解请看别的题解。

简要题意

给定一个数组 \{a_1, \dots, a_n\}，有 q 次询问（l, r, L, R, p, x），并回答 a_l\sim a_r 中有多少个 a_i 满足 L \le a_i \le R 且 a_i \bmod p = x。

强制在线。

看到 a_i \bmod p = x 就可以想到使用根号分治。

考虑将值域作为下标，存储该数值在 a 中的位置：

std::vector<int> vtop[V];
for (int i = 1; i <= n; ++ i) cin >> a[i];
for (int i = 1; i <= n; ++ i) vtop[a[i]].emplace_back(i);

设阈值为 B（一般另 B = \sqrt V，V 为值域）。

当模数 p > B 时，最多只要枚举 \frac{V}{P} 个可能的 a_i 满足条件，所以直接暴力。我们可以枚举每一个 a_i，在 a_i 的所有可能的下标中用二分找到左端点（lpos）和右端点（rpos），答案即为 rpos - lpos + 1，代码如下：

if (p > B) {
  for (int i = (L - x + p - 1) / p * p + x; i <= R; i += p)
    ans += (upper_bound(vtop[i].begin(), vtop[i].end(), r) - vtop[i].begin()) - (lower_bound(vtop[i].begin(), vtop[i].end(), l) - vtop[i].begin());
    // 这里没有 +1 是因为 upper_bound 会找到 rpos 右边一格，所以 upper_bound 这里返回的是 rpos + 1
  cout << ans << "\n";
}

当模数 p \le B 时，我们可以对下标进行分块。创建一个 vector 数组 d_{id, p, x} 预处理出 a_{id_l}\sim a_{id_r}（id_l 和 id_r 分别表示该块的左端点和右端点）中满足 a_i \bmod p = x 的所有 a_i 组成的序列，代码如下：

for (int i = 1; i <= n; ++ i) {
  const int bl_id = (i - 1) / Block_N + 1; // 该下标对应的块编号
  for (int p = 1; p <= Block_V; ++ p)
    d[bl_id][p][a[i] % p].emplace_back(a[i]);
}

然后不能忘记排序：

for (int i = 0; i <= bl(n); ++ i)
  for (int p = 0; p <= Block_V; ++ p)
    for (int x = 0; x <= Block_V; ++ x)
      sort(d[i][p][x].begin(), d[i][p][x].end());

在被询问时就很显然了：

else { // if (p <= B)
  if (bl(l) == bl(r)) { // 左端点和右端点在同一个块，特殊处理
    for (int i = l; i <= r; ++ i) ans += L <= a[i] && a[i] <= R && a[i] % p == x;
    cout << ans << "\n";
  } else {
    while ((l - 1) % Block_N) L <= a[l] && a[l] <= R && a[l] % p == x && ++ ans, ++ l;
    while (r % Block_N)       L <= a[r] && a[r] <= R && a[r] % p == x && ++ ans, -- r;
    // ↑不是完整的块，暴力处理
    for (int i = bl(l); i <= bl(r); ++ i)
      ans += (upper_bound(d[i][p][x].begin(), d[i][p][x].end(), R) - d[i][p][x].begin()) - (lower_bound(d[i][p][x].begin(), d[i][p][x].end(), L) - d[i][p][x].begin());
    // 完整的块，直接相加（没有 +1 的原因和上面同理）
    cout << ans << "\n";
  }
}

然后我们终于写完了这份代码，并获得了 10 分的高分！

%:import "functional"
%:import "algorithm"
%:import "iostream"
%:import "string.h"
%:import "queue"
%:define For(a, b, c) for (int a = b, a##END = c; a <= a##END; ++ a)
%:define bl(x) (((x) - 1) / Block_N + 1)
%:define bl_l(b) ((b) * Block_N - Block_N + 1)
%:define bl_r(b) ((b) * Block_N)
const int N = 1e5 + 7, V = 2e5 + 7, Block_V = 100, Block_N = 316; // Block_V 就是上文写道的 B，这里用于和 Block_N 进行区分

int a[N];
std::vector<int> vtop[V];
std::vector<int> d[318][Block_V + 1][Block_V + 1];
main() {
  using namespace std;
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, type, lastans = 0; cin >> n >> type;

  for (int i = 1; i <= n; ++ i) {
    cin >> a[i], vtop[a[i]].emplace_back(i);
    const int bl_id = (i - 1) / Block_N + 1;
    for (int p = 1; p <= Block_V; ++ p)
      d[bl_id][p][a[i] % p].emplace_back(a[i]);
  }
  for (int i = 0; i <= Block_N; ++ i)
    for (int p = 0; p <= Block_V; ++ p)
      for (int x = 0; x <= Block_V; ++ x)
        sort(d[i][p][x].begin(), d[i][p][x].end());
  int T; cin >> T;
  while (T --) {
    int l, r, L, R, p, x, ans = 0; cin >> l >> r >> L >> R >> p >> x;
    if (type) l ^= lastans, r ^= lastans, L ^= lastans, R ^= lastans, p ^= lastans, x ^= lastans;
    if (p > Block_V)
      for (int i = (L - x + p - 1) / p * p + x; i <= R; i += p)
        ans += (upper_bound(vtop[i].begin(), vtop[i].end(), r) - vtop[i].begin()) - (lower_bound(vtop[i].begin(), vtop[i].end(), l) - vtop[i].begin());
    else {
      if (bl(l) == bl(r)) {
        for (int i = l; i <= r; ++ i) ans += L <= a[i] && a[i] <= R && a[i] % p == x;//, fprintf(stderr, "%d, ", a[i] % p);
        goto opt;
      }
      while ((l - 1) % Block_N) ans += L <= a[l] && a[l] <= R && a[l] % p == x, ++ l;
      while (r % Block_N)       ans += L <= a[r] && a[r] <= R && a[r] % p == x, -- r;
      for (int i = bl(l), iEND = bl(r); i <= iEND; ++ i)
        ans += (upper_bound(d[i][p][x].begin(), d[i][p][x].end(), R) - d[i][p][x].begin()) - (lower_bound(d[i][p][x].begin(), d[i][p][x].end(), L) - d[i][p][x].begin());
    }
    opt: cout << (lastans = ans) << "\n";
  }
}

为什么？

因为这道题时间和空间卡得很紧，连正解都要卡常，更何况非正解呢？

以下是我们需要注意的地方：

由于 p\le B 的部分常数比较大，所以不能使用传统的 \sqrt V 作为阈值，而要使用更小的数，比如 100。
询问区间（L 和 R）不一定是从 1\sim V 的，事实上可能长度远小于 V，所以我们还可以加上判断 if (p > B || (R - ((L - x + p - 1) / p * p + x)) <= 32768)。
当 d[i][j][k].size() <= 1 时，根本不需要排序，排序就是浪费时间，所以我们要在排序前写上：if (d[i][j][k].size() > 1)。
对于 for (int p = 1; p <= B; ++ p) 这里，由于 p\in[1,100]，我们完全可以手写 100 遍代替一个 for 循环。

经过无数次的尝试，我们终于得到了以下 AC 代码，并愉快地切掉了一道黑题（Record）：

#import "algorithm" // 码风过丑，勿喷
#import "iostream"
#import "vector"
#define For(a, b, c) for (int a = b, a##END = c; a <= a##END; ++ a)
#define bl(x) (((x) - 1) / Block_N + 1)
#define bl_l(b) ((b) * Block_N - Block_N + 1)
#define bl_r(b) ((b) * Block_N)
const int N = 1e5 + 7, V = 2e5 + 7, Block_V = 100, Block_N = 750;
int a[N];
std::vector<int> vtop[V];
std::vector<int> d[bl(100000) + 2][Block_V + 1][Block_V + 1];
main() {
  using namespace std;
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, type; cin >> n >> type;

  for (int i = 1; i <= n; ++ i) cin >> a[i];
  for (int i = 1; i <= n; ++ i) vtop[a[i]].emplace_back(i);
  for (int i = 1; i <= n; ++ i) {
    const int bl_id = (i - 1) / Block_N + 1;
#define op(p) d[bl_id][p][a[i] % p].emplace_back(a[i])
    op(1), op(2), op(3), op(4), op(5), op(6), op(7), op(8), op(9), op(10), op(11), op(12), op(13), op(14), op(15), op(16), op(17), op(18), op(19), op(20), op(21), op(22), op(23), op(24), op(25), op(26), op(27), op(28), op(29), op(30), op(31), op(32), op(33), op(34), op(35), op(36), op(37), op(38), op(39), op(40), op(41), op(42), op(43), op(44), op(45), op(46), op(47), op(48), op(49), op(50), op(51), op(52), op(53), op(54), op(55), op(56), op(57), op(58), op(59), op(60), op(61), op(62), op(63), op(64), op(65), op(66), op(67), op(68), op(69), op(70), op(71), op(72), op(73), op(74), op(75), op(76), op(77), op(78), op(79), op(80), op(81), op(82), op(83), op(84), op(85), op(86), op(87), op(88), op(89), op(90), op(91), op(92), op(93), op(94), op(95), op(96), op(97), op(98), op(99), op(100);
  }
  for (int i = 0; i <= bl(n); ++ i)
    for (int p = 0; p <= Block_V; ++ p)
      for (int x = 0; x <= Block_V; ++ x)
        if (d[i][p][x].size() > 1) sort(d[i][p][x].begin(), d[i][p][x].end());
  int T, ans = 0; cin >> T;
  while (T --) {
    int l, r, L, R, p, x; cin >> l >> r >> L >> R >> p >> x;
    type && (l ^= ans, r ^= ans, L ^= ans, R ^= ans, p ^= ans, x ^= ans), ans = 0;
    if (p > Block_V || (R - ((L - x + p - 1) / p * p + x)) <= 32768) {
      for (int i = (L - x + p - 1) / p * p + x; i <= R; i += p)
        ans += (upper_bound(vtop[i].begin(), vtop[i].end(), r) - vtop[i].begin()) - (lower_bound(vtop[i].begin(), vtop[i].end(), l) - vtop[i].begin());
      cout << ans << "\n";
    }
    else {
      if (bl(l) == bl(r)) {
        for (int i = l; i <= r; ++ i) ans += L <= a[i] && a[i] <= R && a[i] % p == x;//, fprintf(stderr, "%d, ", a[i] % p);
        cout << ans << "\n";
      } else {
        while ((l - 1) % Block_N) L <= a[l] && a[l] <= R && a[l] % p == x && ++ ans, ++ l;
        while (r % Block_N)       L <= a[r] && a[r] <= R && a[r] % p == x && ++ ans, -- r;
        for (int i = bl(l), iEND = bl(r); i <= iEND; ++ i)
          ans += (upper_bound(d[i][p][x].begin(), d[i][p][x].end(), R) - d[i][p][x].begin()) - (lower_bound(d[i][p][x].begin(), d[i][p][x].end(), L) - d[i][p][x].begin());
        cout << ans << "\n";
      }
    }
  }
}

~~卡常不易~~，点个赞再走吧~

对了，请不要抄题解，因为你抄了也过不了，就是浪费时间（别问我怎么知道的）