rt，AI 写了个暴力通过了本题

原回答：

为了解决这个问题，我们需要处理两种类型的事件：灵异事件和监控事件。灵异事件会增加特定房子的闹鬼次数，而监控事件会安装监控器，当被监控房子的闹鬼次数达到阈值时触发报警。由于数据规模较大，我们需要高效的算法来处理这些事件。

方法思路

1. 质因数分解优化：预处理每个数的最小质因子，以加速质因数分解过程。
2. 数据结构优化：使用数组存储每个质因子对应的监控器列表，提高访问效率。
3. 处理阈值为0的监控器：使用队列管理阈值为0的监控器，确保它们在下一次灵异事件时立即触发。
4. 高效事件处理：在灵异事件处理过程中，直接更新监控器的总次数并检查触发条件，避免重复处理。

解决代码

#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <algorithm>
#include <cstdint>

using namespace std;

struct Monitor {
    int id;
    uint64_t threshold;
    uint64_t current_sum;
    bool active;
    vector<int> factors; // 监控的质因子列表
};

vector<int> spf; // 最小质因数数组

// 获取x的质因数（不超过n的）
set<int> get_prime_factors(int x, int n) {
    set<int> factors;
    if (x <= 1) return factors;
    while (x != 1) {
        int p = spf[x];
        if (p > n) break;
        factors.insert(p);
        while (x % p == 0) {
            x /= p;
        }
    }
    return factors;
}

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

    int n, m;
    cin >> n >> m;

    // 预处理最小质因数
    spf.resize(n + 1);
    for (int i = 0; i <= n; ++i)
        spf[i] = i;
    for (int i = 2; i * i <= n; ++i) {
        if (spf[i] == i) {
            for (int j = i * i; j <= n; j += i) {
                if (spf[j] == j)
                    spf[j] = i;
            }
        }
    }

    vector<uint64_t> haunted_counts(n + 1, 0);
    vector<vector<Monitor*>> prime_monitors(n + 1); // 每个质因数对应的监控器
    deque<Monitor*> y_zero_queue; // 阈值为0的监控器队列

    vector<Monitor> monitors; // 所有监控器
    monitors.reserve(m);

    uint32_t prev_k = 0;
    int monitor_id = 1;

    while (m--) {
        int op;
        uint32_t x, y_prime;
        cin >> op >> x >> y_prime;

        uint64_t y_real = y_prime ^ prev_k;

        if (op == 0) { // 灵异事件
            vector<int> triggered;

            // 处理阈值为0的监控器
            while (!y_zero_queue.empty()) {
                Monitor* mon = y_zero_queue.front();
                y_zero_queue.pop_front();
                if (mon->active) {
                    triggered.push_back(mon->id);
                    mon->active = false;
                }
            }

            set<int> S = get_prime_factors(x, n);

            // 更新每个质因数对应的监控器
            for (int s : S) {
                if (s > n) continue;
                haunted_counts[s] += y_real;
                // 遍历所有监控该质因数的监控器
                for (Monitor* mon : prime_monitors[s]) {
                    if (!mon->active) continue;
                    mon->current_sum += y_real;
                    if (mon->current_sum >= mon->threshold) {
                        triggered.push_back(mon->id);
                        mon->active = false;
                    }
                }
            }

            // 去重并排序
            sort(triggered.begin(), triggered.end());
            triggered.erase(unique(triggered.begin(), triggered.end()), triggered.end());

            prev_k = triggered.size();

            if (triggered.empty()) {
                cout << "0\n";
            } else {
                cout << triggered.size() << ' ';
                for (size_t i = 0; i < triggered.size(); ++i) {
                    if (i > 0) cout << ' ';
                    cout << triggered[i];
                }
                cout << '\n';
            }
        } else { // 监控事件
            set<int> S = get_prime_factors(x, n);
            vector<int> factors(S.begin(), S.end());
            if (y_real == 0) {
                // 阈值为0，加入y_zero队列
                monitors.emplace_back(Monitor{monitor_id++, 0, 0, true, factors});
                y_zero_queue.push_back(&monitors.back());
            } else {
                // 创建新监控器，current_sum初始为0
                monitors.emplace_back(Monitor{monitor_id++, y_real, 0, true, factors});
                Monitor* new_mon = &monitors.back();
                for (int s : S) {
                    if (s <= n) {
                        prime_monitors[s].push_back(new_mon);
                    }
                }
            }
        }
    }

    return 0;
}

代码解释

1. 预处理最小质因数：使用筛法预处理每个数的最小质因子，加速质因数分解。
2. 数据结构：
   • haunted_counts：记录每个质因子的闹鬼次数。
   • prime_monitors：每个质因子对应的监控器列表。
   • y_zero_queue：存储阈值为0的监控器，这些监控器会在下一次灵异事件触发。
3. 事件处理：
   • 灵异事件：处理阈值为0的监控器，更新相关质因子的闹鬼次数，并检查所有监控这些质因子的监控器是否触发报警。
   • 监控事件：根据阈值是否为0，安装监控器并记录到对应的数据结构中。
4. 去重与排序：确保输出的监控器ID唯一且有序。

该代码通过合理的数据结构和事件处理逻辑，将时间复杂度控制在可接受范围内，适用于大规模数据。

---

https://www.luogu.com.cn/record/201251279