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

· · 题解

简单题，第一部分做的比critnos的题解弱智但是也能过，第二部分比他的简单一点。

考虑怎么刻画题目给的这个东西，容易发现我们其实是要找到最后离开餐厅的感染者 Q，然后把从初始感染者 P 进入餐厅的时刻 S 到最后感染者 Q 离开的时间 T 这段时间内的感染者全部找出来。

那么首先考虑怎么找到最后一个人，这是比较容易的。首先特判掉初始感染者传染不了任何人的情况（R-L<X）。一个显然的观察是，随着 X 减小，最后一个感染者离开的时间是单调不降的。不妨对每个人钦定一个唯一的后继，具体的，对于第 i 个人，我们找到一个 j 使得 R_j > R_i 并且 L_j 最小，然后钦定 j 是 i 的后继，这样我们就可以倍增维护向跳需要的最大 X 值。

那么接下来我们需要维护的是有多少个 [L,R] 与 [S,T] 的交不小于 X。这是容易的，注意到符合条件的区间一定满足 S+X\leq R\leq T 并且长度不小于 X，因为由第一部分可知不存在右端点大于 T 的符合条件区间。这是二维偏序，扫描线即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
    ll L,R;
}t[100005];
ll n,m,p[100005],f[18][100005],g[18][100005],b[400005],tot;
bool cmp(ll A,ll B)
{
    return t[A].R < t[B].R;
}
struct quest{
    ll L,R,X;
}q[100005];
vector<quest> v[400005];
vector<ll> c[400005];
ll d[400005];
void update(ll x)
{
    while(x <= tot)
        d[x]++,x += (x & (-x));
}
ll query(ll x)
{
    ll ret = 0;
    while(x)
        ret += d[x],x -= (x & (-x));
    return ret;
}
ll ans[100005];
int main()
{
    scanf("%lld",&n);
    for(ll i = 1;i <= n;i++)
        scanf("%lld%lld",&t[i].L,&t[i].R),p[i] = i,b[++tot] = t[i].R,b[++tot] = t[i].R - t[i].L;
    sort(p + 1,p + 1 + n,cmp);
    ll pos = n,to = p[n];
    for(ll i = n;i;i--)
    {
        while(pos > 0 && t[p[pos]].R > t[p[i]].R)
        {
            if(t[p[pos]].L < t[to].L)
                to = p[pos];
            pos--;
        }
        f[0][p[i]] = to,g[0][p[i]] = t[p[i]].R - t[to].L;
        for(ll j = 1;j < 18;j++)
            f[j][p[i]] = f[j - 1][f[j - 1][p[i]]],g[j][p[i]] = min(g[j - 1][p[i]],g[j - 1][f[j - 1][p[i]]]);
    }
    scanf("%lld",&m);
    for(ll i = 1;i <= m;i++)
    {
        ll P,X;
        scanf("%lld%lld",&P,&X);
        if(t[P].R - t[P].L < X)
        {
            ans[i] = 1;
            continue;
        }
        ll tmp = P;
        for(ll j = 17;j >= 0;j--)
            if(g[j][tmp] >= X)
                tmp = f[j][tmp];
        q[i] = {t[P].L + X - 1,t[tmp].R,X},b[++tot] = t[P].L + X - 1,b[++tot] = X - 1;
    }
    sort(b + 1,b + 1 + tot);
    tot = unique(b + 1,b + 1 + tot) - b - 1;
    for(ll i = 1;i <= m;i++)
    {
        if(ans[i])
            continue;
        ll t1 = lower_bound(b + 1,b + 1 + tot,q[i].L) - b;
        ll t2 = lower_bound(b + 1,b + 1 + tot,q[i].R) - b;
        ll t3 = lower_bound(b + 1,b + 1 + tot,q[i].X - 1) - b;
        v[t1].push_back({t3,-1,i}),v[t2].push_back({t3,1,i});
    }
    for(ll i = 1;i <= n;i++)
    {
        ll t1 = lower_bound(b + 1,b + 1 + tot,t[i].R) - b;
        ll t2 = lower_bound(b + 1,b + 1 + tot,t[i].R - t[i].L) - b;
        c[t1].push_back(t2);
    }
    ll ccnt = 0;
    for(ll i = 1;i <= tot;i++)
    {
        for(auto j : c[i])
            update(j),ccnt++;
        for(auto j : v[i])
            ans[j.X] += j.R * (ccnt - query(j.L));
    }
    for(ll i = 1;i <= m;i++)
        printf("%lld\n",ans[i]);
    return 0;
}