感染シミュレーション / Infection Simulation JOIG 2024

WZH2026-10-222026-10-22

[JOIG 2024] 感染シミュレーション / Infection Simulation

有 $n$ 个顾客，第 $i$ 的顾客存在时间为 $[l_i,r_i]$ 。

如果一个顾客 $i$ 存在的时间中，与被感染的顾客一起存在了 $\ge x$ 的时间，那么顾客 $i$ 也会被感染。

多次询问，每次给定 $p,x$ ，求如果 $p$ 顾客被感染了，且给定感染系数为 $x$ ，有多少个顾客会被感染。

$n\le 10^5$ 。

子任务： $p=1$ ，且 $l,r$ 随 $i$ 单调不减。

要想充要的转化。

先看子任务。

此时顾客 $1$ 会最先被感染。然后根据 $l,r$ 单调不降，感染顺序一定是 $1,2,\cdots$ 。那么只需要满足相邻两个能传染即可，可以使用 ST 表 $\mathcal{O}(\log n)$ 的查询。

接着看正解。

首先我们肯定要将 $l$ 为第一关键字， $r$ 会第二关键字排序。接下来讨论的下标均为排序后的下标。

引理 1：

存在顾客被感染的时间必然连续。

证明：

考虑第一个被 $p$ 感染的人，其感染前必然存在感染的人 $p$ ，其感染后必然其出现的所有时间都有人感染。

因此归纳可证感染时间必然连续。

通过子任务也可以轻松观察出来。

接下来考虑 $i\ne p$ 感染的充分条件是什么。先提前特判 $r_p-l_p\ge x$ 。

如果说 $i<p$ ，那么条件肯定是 $l_p+x\le r_i$ 。因此这一部分可以直接树桩数组扫描线解决。

接下来看 $i>p$ 的部分。

首先如果 $i$ 被感染，那么必然有 $r_i-l_i\ge x$ ，不然 $i$ 就没有足够的时间被传染了。

然后 $i$ 必须和感染的人在一起。因此考虑 $j<i$ 且 $j$ 被感染，那么 $j$ 能感染 $i$ 的充要条件是 $r_j-l_i\ge x$ 。

最后， $j$ 由于 $j<i$ ，那么 $l_j\le l_i$ ，因此我只要取 $r_j$ 最大的 $j$ 即可。因为引理 1 可知有感染者的时间连续，那么既然 $i$ 需要被感染，那么前面的时间都应该被感染，也就是说，位于 $p\le j<i$ 的 $j$ ，只要 $r_j-l_j\ge x$ 则必然被感染。又因为 $j$ 为 $r_j$ 最大的，于是如果不满足 $r_j-l_j\ge x$ 则 $r_j-l_i\ge x$ 也不成立。于是这个转化就是充要的。

定义 $R_i$ 表示 $\max\limits_{j<i}\{r_j\}$ ，那么 $i$ 被感染的充要条件为：

r_i-l_i\ge x\land R_i-l_i\ge x

注意引理 1，感染的区间需要连续。因此 $i$ 被感染还需要对于任意的 $p<j<i$ ，有 $R_j-l_j\ge x$ 。

接下来我们只要处理这个即可。

套路的枚举 $x$ 扫描线。使用树桩数组维护所有顾客是否满足 $r_i-l_i\ge x$ ，同时使用 set 记录所有不满足 $R_i-l_i\ge x$ 的 $i$ 。

那么每次询问时只需要 upper_bound 第一个 $>i$ 的数 $t$ ，答案就累加 $(p,t)$ 中 $r_i-l_i\ge x$ 的数的个数。

最后加上 $p$ 自己即可。

#include <bits/stdc++.h>
using namespace std;
const int N=400010;
int ans[N],n,m,L[N],R[N],am[N],ss,c[N],p[N],np[N],R2[N],len[N];
struct node{int x,y;}q[N];
int get(int x){return lower_bound(am+1,am+1+ss,x)-am;}
int nn;
void clear(int n){nn=n;for(int i=1;i<=n;i++)c[i]=0;}
void add(int x,int y){for(int i=x;i<=nn;i+=(i&-i))c[i]+=y;}
int query(int x){int cnt=0;for(int i=x;i>=1;i-=(i&-i))cnt+=c[i];return cnt;}
int query(int l,int r){return l>r?0:query(r)-query(l-1);}
vector<node>v[N],V[N];
set<int>S;
using pii=pair<int,int>;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",L+i,R+i),am[++ss]=L[i],am[++ss]=R[i],len[i]=R[i]-L[i];
    sort(am+1,am+1+ss);ss=unique(am+1,am+1+ss)-am-1; 
    for(int i=1;i<=n;i++)L[i]=get(L[i]),R[i]=get(R[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&q[i].x,&q[i].y);
    for(int i=1;i<=n;i++)p[i]=i;
    sort(p+1,p+1+n,[](int x,int y){return L[x]==L[y]?R[x]<R[y]:L[x]<L[y];});
    for(int i=1;i<=n;i++)np[p[i]]=i;
    for(int i=1;i<=m;i++)if(len[q[i].x]>=q[i].y)
        V[np[q[i].x]-1].push_back({get(am[L[q[i].x]]+q[i].y),i});
    for(int i=1;i<=n;i++)v[np[i]].push_back({R[i],1});
    clear(ss);
    for(int i=1;i<=n;i++){
        for(node j:v[i])add(j.x,j.y);
        for(node j:V[i])ans[j.y]+=query(j.x,ss);
    }
    priority_queue<pii,vector<pii>,greater<pii>>q1,q2;
    R2[1]=-1;
    for(int i=1;i<n;i++)R2[i+1]=max(R2[i],R[p[i]]);
    for(int i=1;i<=n;i++){
        q1.push({am[R[i]]-am[L[i]],np[i]});
        q2.push({am[R2[np[i]]]-am[L[i]],np[i]});
    }
    ss=0;
    for(int i=1;i<=m;i++)am[++ss]=q[i].y;
    sort(am+1,am+1+ss);ss=unique(am+1,am+1+ss)-am-1;
    for(int i=1;i<=ss;i++)v[i].clear();
    for(int i=1;i<=m;i++)if(len[q[i].x]>=q[i].y)
        v[get(q[i].y)].push_back({q[i].x,i});
    S.insert(n+1);
    clear(n);
    for(int i=1;i<=n;i++)add(i,1);
    for(int i=1;i<=ss;i++){
        while(!q1.empty()){
            pii t=q1.top();
            int x=t.second,y=t.first;
            if(y>=am[i])break;
            q1.pop();
            add(x,-1);
        }
        while(!q2.empty()){
            pii t=q2.top();
            int x=t.second,y=t.first;
            if(y>=am[i])break;
            q2.pop();
            S.insert(x);
        }
        for(node j:v[i]){
            int x=j.x,id=j.y;
            int t=*S.upper_bound(np[x]);
            ans[id]+=query(np[x]+1,t-1);
        }
    }
    for(int i=1;i<=m;i++)ans[i]++;
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}