P9801 [NERC2018] King Kog’s Reception 题解

· · 题解

题目传送门

前置知识

线段树

解法

第一眼感觉和 luogu P1083 [NOIP2012 提高组] 借教室 很像。本题同样采用线段树维护，sum_{l,r}(1 \le l \le r \le 10^6) 表示从 l \sim r 时刻内骑士拜访的总时间，maxx_{l,r}(1 \le l \le r \le 10^6) 表示从 l \sim r 时刻内骑士拜访完的最后时间。

build 函数和普通线段树一样。

update 函数和普通单点修改一样。

pushup 函数是本题一个难点。考虑对于从 l \sim r(1 \le l \le r \le 10^6) 时刻，如果左区间 l \sim mid 时刻骑士拜访完的最后时间大于右区间 mid+1 \sim r 时刻的起始点，则右区间 mid+1 \sim r 时刻内所有骑士拜访均要向后推迟，即 tree[rt].maxx=max(tree[lson(rt)].maxx+tree[rson(rt)].sum,tree[rson(rt)].maxx);。

query 函数同理，查询时需要额外记录左区间 l \sim mid 时刻骑士拜访完的最后时间，对于最终时间时需要取 \max，即 max(tree[rt].maxx,tree[rt].sum+maxxx);。最终答案即为最终时间减去起始拜访时间。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long//本题需要开 long long 
#define sort stable_sort 
#define endl '\n'
ll t[400000],d[400000],ans=0;
struct SegmentTree
{
    ll l,r,sum,maxx;
}tree[5000000];
ll lson(ll x)
{
    return x*2;
}
ll rson(ll x)
{
    return x*2+1;
}
void pushup(ll rt)
{
    tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum;
    tree[rt].maxx=max(tree[lson(rt)].maxx+tree[rson(rt)].sum,tree[rson(rt)].maxx);
}
void build(ll rt,ll l,ll r)
{
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r)
    {
        tree[rt].maxx=tree[rt].sum=0;
        return;
    }
    ll mid=(l+r)/2;
    build(lson(rt),l,mid);
    build(rson(rt),mid+1,r);
    pushup(rt);
}
void update(ll rt,ll pos,ll val)
{
    if(tree[rt].l==tree[rt].r)
    {
        tree[rt].sum=val;
        tree[rt].maxx=tree[rt].l+val;
        return;
    }
    else
    {
        ll mid=(tree[rt].l+tree[rt].r)/2;
        if(pos<=mid)
        {
            update(lson(rt),pos,val);
        }
        else
        {
            update(rson(rt),pos,val);
        }
    }
    pushup(rt);
}
ll query(ll rt,ll l,ll r,ll maxxx)
{
    if(l<=tree[rt].l&&tree[rt].r<=r)
    {
        return max(tree[rt].maxx,tree[rt].sum+maxxx);
    }
    else
    {
        ll mid=(tree[rt].l+tree[rt].r)/2;
        if(l<=mid)
        {
            ans=max(ans,query(lson(rt),l,r,maxxx));
        }
        if(mid<r)
        {
            ans=max(ans,query(rson(rt),l,r,ans));
        }
        return ans;
    }
}
int main()
{
    ll q,n,i,val;
    char pd;
    cin>>q;
    build(1,1,1000000);
    for(i=1;i<=q;i++)
    {
        cin>>pd;
        if(pd=='+')
        {
            cin>>t[i]>>d[i];
            update(1,t[i],d[i]);//因为第i位骑士访谈的时间是t[i]到t[i]+d[i]
        }
        if(pd=='-')
        {   
            cin>>val;
            update(1,t[val],0);
        }
        if(pd=='?')
        {
            cin>>val;
            ans=0;
            cout<<max(0ll,query(1,1,val,ans)-val)<<endl;
        }
    }
    return 0;
}

后记

双倍经验：P9801 | CF1089K