不出意外的话，这就是我最后的波纹了吧。
当然以后还会继续的。
减半警报器
这个 trick 能将 \(n^2\) 的东西硬生生优化到 \(n\log^2\) ，还是很厉害的 trick
P7603 [THUPC2021] 鬼街
Description
鬼街上经常有灵异事件，每个灵异事件会导致编号为 \(x\) 的质因子的房子闹 \(y\) 次鬼，鬼街上也会装警报器，一个警报器会在其安装后统计编号为 \(x\) 的质因子的房子闹鬼次数总和，这个值达到 \(y\) 时就会报警。特别的，当 \(y = 0\) 时，下一个灵异事件发生时这个警报器就会报警，无论灵异事件的参数如何。要求每个灵异事件会触发的警报器数量以及被触发警报器的编号。
每次输入的 \(y=y'\oplus lastans\) ， \(lastans\) 初始为 \(0\) ，在每次灵异事件后变为本次灵异事件会触发的警报器数量，即询问在线。
\(n,q\leq 10^5,0\leq y\leq 2^{32}\)
Solution
考虑到每次的质因数个数函数 \(\omega(n)\) 在数据范围内不会超过 \(6\) ，所以考虑在装警报器时直接在这不超过 \(6\) 个位置丢一个小警报器，每次灵异事件时就查一遍所有警报器所属的小警报器计数之和是否达到报警阈值。这样的做法是 \(O(\omega(n)n^2)\) 的，显然不足以通过。
考虑优化上面的过程，我们发现警报器进行 “拿出来查询，然后再放回去无事发生” 这个过程的次数会非常多，这启发我们要减少这个过程的次数，而优化用到了一个性质：根据鸽巢原理，如果触发警报，那么所有小警报器计数的最大值一定大于 \(\left\lceil\dfrac y{\omega(x)}\right\rceil\) 。所以我们不需要每一次都处理每一个存在的警报器，而是 设置一个分阈值 ，每一次询问只处理那些到达这一“分阈值”的小警报器的小警报器。但是做到这一步也只相当于在复杂度上乘一个常数，并没有优化，甚至因为“分阈值”这一额外信息的维护而多了一只 \(\log\) 。
还是继续考虑 “拿出来查询，然后再放回去无事发生” 这一过程，我们刚刚对 “拿出来” 的条件进行了优化，而 “放回去” 还没有被我们优化。很自然地，我们会考虑放回去的时候通过 更新分阈值 的方法减少次数：即把旧的阈值减去这一趟所有小警报器的计数和，然后将这一新阈值用同样的方法设置分阈值丢回去。因为每一次最坏的情况是只有达到分阈值的那个小警报器计数为分阈值，其他小警报器计数为 \(0\) ，这样相当于总阈值只减小为原来的 \(\dfrac {\omega(x)-1}{\omega(x)}\) 。
这样一来我们执行 “拿出来查询，然后再放回去无事发生” 这一过程的次数只会有以 \(\dfrac {\omega(x)-1}{\omega(x)}\) 为底的对数次，也就是说我们成功的将复杂度从 \(O(n^2)\) 降到了 \(O(n\log n\log V)\) ， \(\log n\) 来自维护分阈值所需的数据结构， \(\log V\) 则是我们刚刚分析的关于值域的底数。
这个 trick 的理论分析就是这些，本质在于 设置阈值和更新阈值 所带来的复杂度优化。具体如何维护这一过程可以看代码。
Code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define vi vector<int>
#define eb emplace_back
#define pli pair<LL, int>
#define fi first
#define se second
#define rep(rp,a,b) for(int rp=a;rp<=b;++rp)
#define per(bl,a,b) for(int bl=a;bl>=b;--bl)
#define segc int mid = L+R>>1, lc = now<<1, rc = lc|1
const int N = 1e5+5, MOD = 998244353, INF = 1e9;
inline LL read() {
LL x = 0, f = 1; char ch = 0;
while (!isdigit(ch)) {ch = getchar(); if (ch == '-') f = -1;}
while (isdigit(ch)) x = (x<<3)+(x<<1)+(ch^48), ch = getchar();
return f*x;
}
struct BLCK{
int id, opid; LL lim;//监视器编号、阈值编号与阈值
bool operator<(const BLCK &x) const {
return lim > x.lim;
}
};
int n, m, vis[N], cntn, nop[N];//nop i标记监视器i最新阈值编号
LL cnt[N];//从开始到现在闹鬼的次数
vi pri[N], ans;
priority_queue<BLCK> q[N];
pair<int, LL> mon[N];//每个监视器的监视目标和阈值
void sieve() {
rep (i, 2, n) {
if (!pri[i].empty()) continue ;
rep (j, 1, n/i) pri[i*j].eb(i);
}
}
LL getval(int x) {
LL ret = 0;
for (int j:pri[mon[x].fi]) ret += cnt[j];
return ret;
}
int main() {
n = read(), m = read();
sieve();
LL lans = 0;
while (m --) {
int opt = read(), x = read();
LL y = read()^lans;
if (!opt) {
for (int i:pri[x]) cnt[i] += y;
for (int i:pri[x]) {
while (!q[i].empty() && q[i].top().lim <= cnt[i]) {
BLCK x = q[i].top(); q[i].pop();
if (vis[x.id]) continue ;
if (nop[x.id] != x.opid) continue ;//类似dij的懒删除堆，忽略编号不为最新的阈值
LL newval = getval(x.id);
if (newval >= mon[x.id].se) vis[x.id] = 1, ans.eb(x.id);
else {
LL newlim = (mon[x.id].se-newval-1)/pri[mon[x.id].fi].size()+1;
++nop[x.id];
for (int j:pri[mon[x.id].fi])
q[j].push((BLCK){x.id, nop[x.id], newlim+cnt[j]});
}
}
}
sort(ans.begin(), ans.end());
printf("%d", (int)ans.size());
for (int i:ans) printf(" %d", i); puts("");
lans = ans.size();
ans.clear();
} else {
++cntn;
if (!y) {
ans.eb(cntn);
continue ;
}
LL lim = (y-1)/pri[x].size()+1, stp = 0;
++nop[cntn];
for (int i:pri[x]) {
q[i].push((BLCK){cntn, nop[cntn],lim+cnt[i]});
stp += cnt[i];
} mon[cntn] = mp(x, y+stp);
}
}
return 0;
}
Summary
很经典的 trick （according to Cust10），但是优化幅度不算大，所以对应的数据范围也是比较好看出来的。