Day \(\text{M}_r(\text{O}_2)\)。
这东西原来叫减半报警器？？
首先这题肯定和数论没啥关系，因为 \(10^5\) 之内的 \(\max \omega(n)=6\)，即一个数至多只有 \(6\) 个质因子。
然后我们发现如果 \(x\) 有 \(k\) 个不同的质因子，这 \(k\) 个质因子代表的房子内闹鬼总次数达到了 \(y\)，那么至少有一个房子内闹鬼次数达到 \(\left\lceil y/k\right\rceil\)。换而言之，检测房子闹鬼次数达到 \(\left\lceil y/k\right\rceil\) 就是报警的必要条件。
那么我们把每个报警器 \((x,y)\) 拆分成更小的报警器：
- 在 \(x\) 的 \(k\) 个不同质因子 \(d\) 代表的房子上安装一个阈值为 \(t=\left\lceil y/k\right\rceil+s_d\) 的小报警器 \((d,t)\)。\(s_d\) 为目前房子 \(d\) 的闹鬼次数，当闹鬼总次数达到 \(t\) 时激活小报警器。
- 在每一个房子 \(d\) 处用一个小根堆来维护这个房子所有的小报警器 \((d,t)\)，按照阈值 \(t\) 从小到大排序。当这栋房子闹鬼时，就可以从小到大找到所有阈值不超过总闹鬼次数的报警器。
- 一旦有一个 \((d,t)\) 小报警器被触发，意味着其所在的报警器可能已经报警了，直接暴力检查；如果没有报警，对应报警器的所有小报警器 \((d',t')\) 重新分配阈值 \(t'=\left\lceil (y-(s_d-t))/k\right\rceil+s_{d'}\)。
不难发现以上的分配方案下，一个报警器至多被重新分配 \(\log_{6/5} y\) 次。
复杂度 \(O(\omega(n)m\log m\log_{6/5}y)\)。
// Problem: P7603 [THUPC2021] 鬼街
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7603
// Memory Limit: 1 MB
// Time Limit: 10000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;
const int N = 1e5 + 100;
int n, m, cnt, vis[N];
int tot, pr[N], vs[N], mf[N], nx[N];
ll res[N], sum[N];
vector<pi> g[N];
vector<int> ans;
priority_queue<pi, vector<pi>, greater<pi> > q[N];
void init(int lim) {
mf[1] = nx[1] = 1;
for (int i = 2; i <= lim; i++) {
if (!vs[i]) pr[++tot] = mf[i] = i, nx[i] = 1;
for (int j = 1; j <= tot && i * pr[j] <= lim; j++) {
vs[i * pr[j]] = 1;
mf[i * pr[j]] = mf[i];
nx[i * pr[j]] = (pr[j] == mf[i]) ? nx[i] : (nx[i] * pr[j]);
if (i % pr[j] == 0) break;
}
}
}
void reb(int x) {
for (auto &i : g[x])
res[x] -= sum[i.se] - i.fi, i.fi = sum[i.se];
if (res[x] <= 0) return vis[x] = 1, ans.pb(x), void();
ll tp = (res[x] + g[x].size() - 1) / g[x].size();
for (auto i : g[x]) q[i.se].push(mp(tp + sum[i.se], x));
}
void add(int x, ll y) {
sum[x] += y;
while (!q[x].empty() && q[x].top().fi <= sum[x]) {
pi tp = q[x].top(); q[x].pop();
if (!vis[tp.se]) reb(tp.se);
}
}
void solve() {
cin >> n >> m, init(1e5);
for (int _ = 1, lst = 0, op, x; _ <= m; _++) {
ll y; cin >> op >> x >> y, y ^= lst;
if (!op) {
for (int i = x; i != 1; i = nx[i]) add(mf[i], y);
lst = ans.size(), sort(ans.begin(), ans.end()), cout << lst << ' ';
for (int i : ans) cout << i << ' '; cout << '\n', ans.clear();
} else {
cnt++, res[cnt] = y;
for (int i = x; i != 1; i = nx[i])
g[cnt].pb(mp(sum[mf[i]], mf[i]));
reb(cnt);
}
}
}
bool Med;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}