题解：P7603 [THUPC2021] 鬼街

· · 题解

折半报警器。第一次看到这个玩意应该是在 gym 102331F。

设 d_x 表示 x 的质因子集合，cnt_i 表示从开始起，i 房间的报警次数。记安装监视器 i 时，其监视的所有房间的 cnt 和为 stp_i，则报警的条件是 \sum_{j\in d_x}cnt_j\geq stp_i+y。每次加入后都判断该条件是否成立，复杂度爆炸。

考虑减少判断次数，引入折半报警器。上述条件等价于 \sum_{j\in d_x}\Delta cnt_j\geq y，也即至少存在一个 j 满足 \Delta cnt_j\geq \lceil \frac{y}{|d_x|}\rceil。因此，我们对每个房间开一个优先队列，记录每一个监视器在该房间处可能报警的 cnt 的阈值。每次更新某个房间的 cnt 时，就 check 它是否达到了某个监视器的报警阈值。若达到了报警阈值，就将计算该监视器当前的总闹鬼次数，判断是否会触发报警，并将该监视器从所有房间的队列里删除。若触发报警，则计入当前答案；否则用现在的 y^{\prime}=stp_i+y- \sum_{j\in d_x}cnt_j 重新设定每个房间的报警阈值，将新的报警阈值 \Delta cnt_j\geq \lceil \frac{y^{\prime}}{|d_x|}\rceil 扔进每个房间的优先队列里即可。

不难发现，每次报警时，一个监视器的 y 都会减少 \frac{1}{|d_x|}，因此共会更新 \log V 个报警阈值，被加入总共 d_x\log V 个优先队列里。总复杂度可以被控制在 O(nd_x\log V\log n)。

堆的删除可以使用懒惰删除，维护每个监视器的最新阈值编号、以及堆中每个阈值信息的编号即可。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define int long long
#define qingbai 666
using namespace std;
typedef long long ll;
const int N=1e5+5,M=105,inf=1e9+7,mo=998244353;
void read(int &p){
    int x=0,w=1;
    char ch=0;
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    p=x*w;
}
int n,m;
vector<int>d[N];
struct node{
    int id,opid,targ;//监视器编号、阈值编号及报警阈值
    friend bool operator<(node x,node y){
        return x.targ>y.targ;
    }
};
priority_queue<node>q[N];
int cnt[N];
pii mon[N];
int stp[N],nop[N];
bool vis[N];
int gets(int x){
    int res=0;
    for(auto j:d[mon[x].fir])
        res+=cnt[j];
    return res;
}
signed main(){
    read(n),read(m);
    rep(i,1,n){
        int x=i;
        rep(j,2,sqrt(i)){
            int cnt=0;
            while(x%j==0)
                x/=j,cnt++;
            if(cnt!=0)d[i].push_back(j);
        }
        if(x!=1)d[i].push_back(x);
    }
    int lans=0,cntm=0;
    vector<int>ans;
    while(m--){
        int op,x,y;
        read(op),read(x),read(y),y^=lans;
        if(op==1){
            cntm++;
            if(!y){
                ans.push_back(cntm);
                continue;
            }
            int targ=(y-1)/d[x].size()+1;
            nop[cntm]++;
            for(auto i:d[x])
                q[i].push((node){cntm,nop[cntm],targ+cnt[i]}),stp[cntm]+=cnt[i];
            mon[cntm]=mp(x,y+stp[cntm]);
        }
        else{
            for(auto i:d[x])
                cnt[i]+=y;
            for(auto i:d[x]){
                while(!q[i].empty()&&q[i].top().targ<=cnt[i]){
                    node nw=q[i].top();
                    q[i].pop();
                    if(vis[nw.id])continue;
                    if(nop[nw.id]!=nw.opid)continue;//懒惰删除 
                    int nws=gets(nw.id);
                    if(nws>=mon[nw.id].sec)vis[nw.id]=1,ans.push_back(nw.id);
                    else{
                        int ntg=(mon[nw.id].sec-nws-1)/d[mon[nw.id].fir].size()+1;
                        nop[nw.id]++;
                        for(auto j:d[mon[nw.id].fir])
                            q[j].push((node){nw.id,nop[nw.id],cnt[j]+ntg});
                    }
                }
            }
            printf("%lld",(int)ans.size());
            sort(ans.begin(),ans.end());
            for(auto i:ans)
                printf(" %lld",i);
            lans=ans.size();
            ans.clear();
            puts("");
        }
    }
    return 0;
}