登录
根号分类讨论（sqrt trick）& 扫描线
2025年8月18日 12:42
解法：根号分类讨论（sqrt trick）& 扫描线
如果 $k_i > \sqrt{n}$，我们直接暴力计算，因为下标每次增加 $\sqrt{n}$，最多加 $\sqrt{n}$ 次就到 $n$ 了。维护这种操作的复杂度是 $\mathcal{O}(q\sqrt{n})$。
如果 $k_i \le \sqrt{n}$，注意到本次操作被修改的下标 $\mod k_i$ 都和 $l_i \bmod k_i$ 相等，又因为只要求最后的答案，所以我们可以把这个信息先分类记下来：步长为 $k_i$，且下标 $\mod k_i$ 为特定值，且位于区间 $[l_i, r_i]$ 里的所有下标都要乘以 $v_i$。步长只有 $\sqrt{n}$ 种，每种步长的 $\bmod$ 也只有 $\sqrt{n}$ 种，因此我们只有 $\mathcal{O}(n)$ 类信息要记录。
怎么把我们记录的信息还原成答案呢？我们枚举每类信息，这样问题变为：每次给一个区间乘以 $v_i$，问每个数最后的值。这就是 leetcode 1109. 航班预定统计，对操作区间排序，使用差分 + 扫描线的思想即可离线处理。1109 题里，加法的逆运算是减法，本题里模意义下乘法的逆运算是求逆元。
还原答案的复杂度是多少呢？注意到相同步长不同余数的下标是不会重复的，因此每种步长会恰好把所有下标枚举一遍，因此我们会枚举 $\mathcal{O}(n\sqrt{n})$ 次下标，再加上对操作的排序，因此复杂度为 $\mathcal{O}(q\log q + n\sqrt{n})$。
最后考虑求逆元的复杂度，整体复杂度为 $\mathcal{O}(q(\log q + \log M) + n\sqrt{n})$，其中 $M = 10^9 + 7$ 是模数。
参考代码（c++）
class Solution {
public:
int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size(), B = sqrt(n);
// 求乘法逆元
const int MOD = 1e9 + 7;
auto inv = [&](long long a) {
long long b = MOD - 2, y = 1;
for (; b; b >>= 1) {
if (b & 1) y = (y * a) % MOD;
a = a * a % MOD;
}
return y;
};
long long A[n];
for (int i = 0; i < n; i++) A[i] = nums[i];
typedef pair<int, long long> pil;
vector<pil> vec[B + 1][B + 1];
for (auto &qry : queries) {
int l = qry[0], r = qry[1], K = qry[2], v = qry[3];
if (K <= B) {
// 步长不超过根号，先把操作记下来
// 差分思想：记录操作开始的位置以及原运算，再记录操作结束的位置以及逆运算
vec[K][l % K].push_back({l, v});
vec[K][l % K].push_back({r + 1, inv(v)});
} else {
// 步长超过根号，暴力处理
for (int i = l; i <= r; i += K) A[i] = A[i] * v % MOD;
}
}
// 枚举每一类操作
for (int k = 1; k <= B; k++) for (int m = 0; m < k; m++) {
// 把操作按下标从左到右排序
sort(vec[k][m].begin(), vec[k][m].end());
// 扫描线维护当前乘积
long long now = 1;
// 枚举这一类里的所有下标
for (int i = m, j = 0; i < n; i += k) {
// 用扫描线进行需要的操作
while (j < vec[k][m].size() && vec[k][m][j].first <= i) {
now = now * vec[k][m][j].second % MOD;
j++;
}
A[i] = A[i] * now % MOD;
}
}
long long ans = 0;
for (int i = 0; i < n; i++) ans ^= A[i];
return ans;
}
};
