题解：P7603 [THUPC2021] 鬼街

· · 题解

题面

根据学长的讲题找到这里。

看懂了，记一下。

减半报警器。

考虑到如果 \sum\limits_{i=1}^ka_i=S，则有 \max\limits_{i=1}^ka_i\ge \left\lceil\dfrac{S}{k}\right\rceil。证明是显然的。

注意到 10^5 以内的数最多只有 6 个质因子，我们考虑对所有质数暴力维护闹鬼的次数，并且及时检查警报器的状态。

具体而言，我们假设一个警报器监视的集合为 d，报警的阈值为 y。由之前的结论，如果某个 x\in d 的房子在其开始监测后闹鬼次数达到了 \left\lceil\dfrac yd\right\rceil 时我们就计算 s=\sum\limits_{x\in d}\Delta cnt_x 并检查一下这个监测器会不会报警。如果发现并没有达到阈值，就将 y 减小，更新对应的阈值（相当于加入一个阈值比之前少 s 的监测器）。这样的话每次阈值都会至少变成原来的 \dfrac {k-1}k，所以一个监测器不成功的检查最多 \log 次。

具体实现就是对于每个质数维护一个堆来记录监测这里的所有监测器的阈值。每次更新后暴力取出所有阈值小于目前 cnt 的检查即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
bool f[100005];
vector<int>d[100005];
void ss(){//筛质数
    for(int i=2;i<=100000;i++){
        if(!f[i]){
            for(int j=i;j<=100000;j+=i){
                f[j]=1;
                d[j].push_back(i);
            }
        }
    }
}
struct node{
    int val,id,tim;
    bool operator<(const node &t)const{return val>t.val;}
};//记录一个加到堆中的阈值的值、对应的监测器以及是否失效
priority_queue<node>q[100005];
int las[100005],tag,num,cnt[100005],a[100005],b[100005],stp[100005];
vector<int>res,zer;
void Sol(node x){//检查一个监测器
    int p=x.id;
    if(las[p]==-1)return;//已报警
    int sum=0;
    for(int v:d[a[p]])sum+=cnt[v];//计算s
    if(sum>=stp[p]+b[p]){//报警了
        res.push_back(p);
        las[p]=-1;
        return;
    }
    b[p]=stp[p]+b[p]-sum;//更新阈值
    stp[p]=sum;//当前值
    las[p]=++tag;//现在使用最新的阈值
    int s=d[a[p]].size(),l=(b[p]+s-1)/s;
    for(int v:d[a[p]]){
        q[v].push(node({cnt[v]+l,p,tag}));
    }
}
void ch(int x){//检查一个堆
    while(!q[x].empty()&&q[x].top().val<=cnt[x]){
        node tmp=q[x].top();
        q[x].pop();
        if(las[tmp.id]!=tmp.tim)continue;//不是最新的
        Sol(tmp);
    }
}
signed main()
{
    ss();
    scanf("%lld%lld",&n,&m);
    int op,x,y;
    while(m--){
        scanf("%lld%lld%lld",&op,&x,&y);
        y^=ans;
        if(op){
            int s=d[x].size();
            int l=(y+s-1)/s;
            tag++;
            num++;
            if(y==0){
                zer.push_back(num);
                continue;
            }
            a[num]=x;
            b[num]=y;
            las[num]=tag;
            for(int v:d[x]){
                stp[num]+=cnt[v];
                q[v].push(node({cnt[v]+l,num,tag}));
            }
        }
        else{
            res.clear();
            for(int v:zer)res.push_back(v);
            zer.clear();
            for(int v:d[x])cnt[v]+=y;
            for(int v:d[x])ch(v);
            sort(res.begin(),res.end());
            ans=res.size();
            printf("%lld ",ans);
            for(int v:res)printf("%lld ",v);
            puts("");
        }
    }
    return 0;
}