THUPC2021 鬼街

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;
}