官方题解｜考拉兹猜想

题目解析

数据结构（平方分割，等）；

编写程序计算，$10^5$ 内变为 $1$，需要操作次数最多的数为 $77031$，经过 $350$ 次操作后变为 $1$。这意味着，数组中的每个元素最多经过 $350$ 次操作后，后续的操作对其失效。

我们考虑将数组分割为 $\sqrt{N}$ 个部分，对于每个块，我们维护一个容器，存储块内不为 $1$ 的元素的下标，另外维护一个变量维护块内为 $1$ 的元素数量。每次修改操作，$[L, R]$：

1. 对于未整体出现在同一个块内的元素，暴力更新。
2. 对于整体出现在同一个块内的元素，只修改块内不为 $1$ 的元素，同时将修改后所有的变为 $1$ 的元素下标，从块内容器中删除，同时令块内为 $1$ 的元素数量增加。

由于每个元素最多被修改 $350$ 次后，变为 $1$，上述操作，第一部分时间复杂度为 $\mathrm{O}(\sqrt{N})$，第二部分同样为 $\mathrm{O}(\sqrt{{N}})$。

对于每个查询 $[L, R]$，也分为两个部分：

1. 对于未整体出现在同一个块内的元素，暴力统计。
2. 对于整体出现在同一个块内的元素，查询块内维护的块内为 $1$ 的元素数量。

两部分操作时间复杂度皆为 $\mathrm{O}(N\sqrt{N})$。

AC代码

#include <bits/stdc++.h>
 
using i64 = long long;
 
template<class T>
class SquareRoot {
private:
    int n, len, cnt;
    std::vector<T> v;
    std::vector<T> sum;
    std::vector<std::vector<int>> block;
    std::vector<int> id;
    std::vector<std::vector<int>> rid;
public:
    SquareRoot() : SquareRoot(0) {}
    explicit SquareRoot(int n) : SquareRoot(std::vector<int>(n)) {}
    explicit SquareRoot(const std::vector<T> &a) : n(a.size()), v(a) {
        len = std::sqrt(n);
        cnt = (n + len - 1) / len;
        sum = std::vector<T>(cnt);
        block = std::vector<std::vector<int>>(cnt);
        id = std::vector<int>(n);
        rid = std::vector<std::vector<int>>(cnt);
        for (int i = 0; i < n; ++i) {
            id[i] = i / len;
            rid[id[i]].push_back(i);
            if (v[i] > 1)
                block[id[i]].push_back(i);
            else
                sum[id[i]] += 1;
        }
    }
 
    bool singalUpdate(int i) {
        if (v[i] == 1) return true;
        if (v[i] & 1)
            v[i] = v[i] * 3 + 1;
        else
            v[i] /= 2;
        if (v[i] == 1) sum[id[i]] += 1;
        return v[i] == 1;
    }
 
    void blockUpdate(int i) {
        std::vector<int> st;
        for (auto &j : block[i])
            if (!singalUpdate(j))
                st.push_back(j);
        block[i] = std::move(st);
    }
 
    void apply(int l, int r) {
        if (l >= r) return;
        int sid = id[l], eid = id[r - 1];
        if (sid == eid) {
            for (int i = l; i < r; ++i)
                singalUpdate(i);
            return;
        }
        for (int i = l; id[i] == sid; ++i)
            singalUpdate(i);
        for (int i = sid + 1; i < eid; ++i)
            blockUpdate(i);
        for (int i = r - 1; id[i] == eid; --i)
            singalUpdate(i);
    }
 
    T prod(int l, int r) {
        if (l >= r) return 0;
        T sm = 0;
        int sid = id[l], eid = id[r - 1];
        if (sid == eid) {
            for (int i = l; i < r; ++i)
                sm += v[i] == 1;
            return sm;
        }
        for (int i = l; id[i] == sid; ++i)
            sm += v[i] == 1;
        for (int i = sid + 1; i < eid; ++i)
            sm += sum[i];
        for (int i = r - 1; id[i] == eid; --i)
            sm += v[i] == 1;
        return sm;
    }
};
 
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    SquareRoot<int> data(a);
    while (q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        if (t == 1)
            data.apply(l, r + 1);
        else
            std::cout << data.prod(l, r + 1) << '\n';
    }
    return 0;
}