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

· · 题解

提供一种比较不要脑子的树套树做法。

先把每个问题拆成两个子问题。子问题一：求出连续感染的最长区间。子问题二：求和连续感染区间有交且交大于 x 的区间数量。

那么显然是要先离线下来的，对于子问题一，左端点排序，先去掉完全被包含的区间，然后处理出每个区间到下一个区间交的大小，做倍增就可以了。

子问题二分为三种情况：左边交（l<L,r \geq L+X），右边交（r>L,l \leq R-X），中间交（l \geq L,r \leq R,r-l \geq X）。

其他条件显然可以做二维偏序，除了 r-l \geq X 比较麻烦。考虑根据区间大小从大往小加入区间，中间去查就可以了。（其实本质上是三维偏序，CDQ 分治也可以做，但显然树套树更好写。）

时间复杂度为 O(n \log^2 n)。

:::info[代码]

#include<bits/stdc++.h>
#define fst first
#define sec second
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pii;
const int maxn=2e5+5;
const int maxm=1e6+5;
const int inf=1e9+1;
void read(int& x){
    char c; while((c=getchar())<48); x=c-48;
    while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;
}
int t[maxm*20],ls[maxm*20],rs[maxm*20],tot=0,n,q,m;
void update(int x,int p,int u,int l=1,int r=m){
    if(l==r){ t[u]+=p; return; }
    int mid=l+r>>1;
    if(x<=mid){
        if(!ls[u]) ls[u]=++tot;
        update(x,p,ls[u],l,mid);
    }
    else{
        if(!rs[u]) rs[u]=++tot;
        update(x,p,rs[u],mid+1,r);
    }
    t[u]=t[ls[u]]+t[rs[u]];
}
int query(int L,int R,int u,int l=1,int r=m){
    if(r<L||l>R||(!u)) return 0;
    if(l>=L&&r<=R) return t[u];
    int mid=l+r>>1;
    return query(L,R,ls[u],l,mid)+query(L,R,rs[u],mid+1,r);
}
int rt[maxm];
void add(int L,int R){
    for(int i=L;i<=m;i+=i&(-i)) update(R,1,rt[i]);
}
int qin(int L,int R){
    int ans=0;
    for(int i=m;i>=1;i-=i&(-i)) ans+=query(1,R,rt[i]);
    for(int i=L-1;i>=1;i-=i&(-i)) ans-=query(1,R,rt[i]);
    return ans;
}
int qout(int L,int R){
    int ans=0;
    for(int i=L;i>=1;i-=i&(-i)) ans+=query(R,m,rt[i]);
    return ans;
}
struct node{
    int l,r,x,tp;
    bool operator<(node a){
        if(x==a.x) return a.tp==0&&tp==0 ? 0 : tp==0;
        else return x>a.x;
    }
};
int f[maxn][21],g[maxn][21],ans[maxn],lst[maxn];
pii a[maxn],b[maxn]; vector<node> v;
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i].fst),read(a[i].sec),a[i].sec=-a[i].sec,b[i]=a[i];
    sort(a+1,a+n+1); int now=1,p=1; vector<int> vi;
    for(int i=1;i<=n;i++) a[i].sec=-a[i].sec;
    while(now<=n){
        while(p<=n&&a[p].sec<=a[now].sec) ++p; vi.push_back(now);
        f[now][0]=p,g[now][0]=(p>n||a[now].sec<=a[p].fst ? -1 : a[now].sec-a[p].fst),now=p;
    }
    for(int i=1;i<=20;i++){
        for(int j : vi){
            f[j][i]=f[f[j][i-1]][i-1],g[j][i]=min(g[j][i-1],g[f[j][i-1]][i-1]);
        }
    }
    for(int i=1;i<=n;i++) lst[i]=(g[i][0] ? i : lst[i-1]);
    for(int i=1;i<=n;i++) v.push_back((node){a[i].fst,a[i].sec,a[i].sec-a[i].fst,0});
    for(int i=1;i<=n;i++) a[i].sec=-a[i].sec;
    read(q);
    for(int i=1;i<=q;i++){
        int p,x; read(p),read(x);
        p=lower_bound(a+1,a+n+1,b[p])-a;
        if(-a[p].sec-a[p].fst<x){ ans[i]=1; continue; }
        int now=lst[p];
        for(int i=20;i>=0;i--){
            if(g[now][i]>=x) now=f[now][i];
        }
        int L=a[p].fst,R=-a[now].sec;
        v.push_back((node){L-1,L+x,x,i});
        v.push_back((node){R-x,R+1,x,i});
        v.push_back((node){L,R,x,-i});
    }
    sort(v.begin(),v.end());
    vector<int> c;
    for(node i : v) c.push_back(i.l),c.push_back(i.r);
    sort(c.begin(),c.end()),c.erase(unique(c.begin(),c.end()),c.end()),m=c.size();
    for(int i=0;i<(int)v.size();i++){
        v[i].l=lower_bound(c.begin(),c.end(),v[i].l)-c.begin()+1;
        v[i].r=lower_bound(c.begin(),c.end(),v[i].r)-c.begin()+1;
    }
    for(int i=1;i<=m;i++) rt[i]=++tot;
    for(node i : v){
        if(i.tp==0) add(i.l,i.r);
        else if(i.tp<0) ans[-i.tp]+=qin(i.l,i.r);
        else if(i.tp>0) ans[i.tp]+=qout(i.l,i.r);
    }
    for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
    return 0;
}

:::