计算子数组中可整除的元素

Question

我正在尝试解决以下练习：

有一个正整数数组，其大小为 N，给定 1 <= N <= 2*10⁵。数组的每个元素始终最多为 10⁵。
读入这N个整数后，需要支持Q个查询（1<= Q <= 10⁵）。

每个查询都会询问以下其中一项：

1. 计数整除性（在输入中用字母Q表示）：
   查找子数组中可被给定输入值整除的元素数量。对于此查询，您将获得 3 个整数：子数组的左端、子数组的右端以及要计算整除性的整数。

2. 更新（由输入中的字母U表示）：
   将某个索引处的元素更改为新值。对于此查询，您将获得 2 个整数：要更改的索引和新值。

我有一个 O(NQ) 的强力解决方案，但它超时了。有什么想法如何以更好的时间复杂度解决这个问题吗？

---

第一行输入的是N和Q。下一行包含数组的所有起始元素，并用空格分隔。

接下来的 Q 行每行包含一个查询。查询的各个部分用空格分隔，索引从 0 开始。

输入示例：

6 4
6 5 4 3 2 1
Q 0 3 1
Q 1 4 2
U 3 8
Q 1 5 2

理想的输出是（每个可整除元素计数的查询应在新行上回答）

4
2
3

我的暴力代码是这样的（但是太慢了）：

#include <iostream>
#include <vector>

int main() {
    using std::cin, std::cout;

    int N, Q;
    cin >> N >> Q;

    std::vector<int> array(N);
    for (int &i : array) cin >> i; // read starting array elements

    for (int q = 0; q < Q; q++) {
        char t;
        cin >> t;
        if (t == 'Q') {
            // query how many numbers in array between index left and right are divisible by num
            int left, right, num;
            cin >> left >> right >> num;
            int cnt = 0;
            for (int i = left; i <= right; i++) {
                if (array[i] % num == 0) {
                    cnt++;
                }
            }
            cout << cnt << '\n'; // don't use endl when there's a lot of output
        } else {
            // simple update on one element in array
            int index, newNum;
            cin >> index >> newNum;
            array[index] = newNum;
        }
    }
    return 0;
}

Answer 1

这可以通过应用平方根分解来解决，以使范围查询和点更新都高效。让我们将数组分成大约 √N 个块，每个块的大小为 √N。

对于每个块，我们可以预先计算块中可被每个可能的查询值（1 到 100000 的整数）整除的元素数量。 我们可以通过迭代到其平方根来找到数字的所有因子，因此我们可以将一个元素添加到

O(√(MAX_ARRAY_ELEMENT))

中的一个块的答案中。初始数组的预计算需要

O(N√(MAX_ARRAY_ELEMENT))

，这是可以接受的，因为

MAX_ARRAY_ELEMENT

至多为

100000

。

要更新索引处的值，我们删除该索引处的当前值对其块的贡献，更新数组，然后将新元素的贡献添加到该块的预先计算值中。这需要

O(√(NEW_VALUE))

。

要计算子数组中可被特定数字整除的元素数量，我们可以将查询的子数组拆分为多个段。子数组的某些部分可能直接被某些块覆盖：最多有 √N 个块，我们可以在恒定时间内得到每个块的答案，因为它们都是预先计算的。最多还有两个部分（在子数组的开头和结尾）仅部分位于块内；为此，我们需要使用强力方法来测试所有元素的可分性，但这两个块中的每一个中最多只有 √N 个元素。 答案是所有这些部分的计数之和。因此，此类查询的时间复杂度为

O(√N)

。

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
constexpr int MAX_ELEM = 1e5;
int main() {
    int N, Q;
    std::cin >> N >> Q;
    int blockSize = std::sqrt(N), numBlocks = (N + blockSize - 1) / blockSize;
    std::vector<int> array;
    array.reserve(N);
    std::vector<std::vector<int>> blockAns(numBlocks, std::vector<int>(MAX_ELEM + 1));
    auto update = [&](int idx, int delta) {
        for (int i = 1, block = idx / blockSize; i * i <= array[idx]; ++i) {
            if (auto [q, r] = std::div(array[idx], i); r == 0) {
                blockAns[block][i] += delta;
                if (q != i) blockAns[block][q] += delta;
            }
        }
    };
    for (int i = 0, x; i < N; ++i) {
        std::cin >> x;
        array.push_back(x);
        update(i, 1);
    }
    for (int q = 0; q < Q; ++q) {
        char t;
        std::cin >> t;
        if (t == 'Q') {
            int left, right, num;
            std::cin >> left >> right >> num;
            int leftBlock = left / blockSize, rightBlock = right / blockSize, count = 0;
            if (leftBlock != rightBlock) {
                for (int i = left; i < blockSize * (leftBlock + 1); ++i) 
                    count += array[i] % num == 0;
                for (int b = leftBlock + 1; b < rightBlock; ++b)
                    count += blockAns[b][num];
                for (int i = rightBlock * blockSize; i <= right; ++i)
                    count += array[i] % num == 0;
            } else {
                for (int i = left; i <= right; ++i)
                    count += array[i] % num == 0;
            }
            std::cout << count << '\n';
        } else {
            int index;
            std::cin >> index;
            update(index, -1);
            std::cin >> array[index];
            update(index, 1);
        }
    }
}