题314.csp-2203 P2出行计划

• 题314.csp-2203 P2出行计划
• 一、题目
• 二、题解

本题给定n个出行的开始时间ti以及出行对应地点需持ci时间内的核酸检测，求对于m个核酸检测时间点询问，在k时间出结果以后最多出行的个数。
暴力求解，十分显然，无非就是对于每次询问，把可出行的时间的上界与下界通过k，q，c算出来，看开始出行时间t是否在那个时间区间内就好，这样每次询问得做n次计算，对于m次询问，时间复杂度自然是平方级别的，不满足本题满分的要求。
对于本题的正解，我们可以用差分＋前缀和。如何想到的？易知，暴力解法，每个出行点可出行需满足的条件为q+k<=ti<=q+k+ci-1,这个条件不是很好用，我们不妨将其变形，化成ti-ci-k+1<=q<=ti-k，推导过程如下：

则问题就变为了看q这个点能够被放在多少个[t-c-k+1,t-k]区间里，但是单纯这样去想又会发现每次询问仍然要拿着q对那n个区间去比对，时间和原先暴力解法一样。此时我们不妨转换思考的角度，看q这个点能够被放在多少个[t-c-k+1,t-k]区间里这个问题其实等价于用n个区间把一堆时间点给覆盖了，看问的那个时间点被多少个区间所覆盖的问题。这样我们其实可以在输入n个出行点信息的时候把对应区间求出，然后把这个区间内所有的时间点对应的结果（即被覆盖数，原先为0）都+1，然后在后面询问的时候，直接输出那个时间点对应的结果就好。那么如何可以快速的将一个区间内的值进行统一的修改呢？显然就会想到差分了。对于给定结果数组对应的差分数组b[l]+1，b[r+1]-1，等价于对其原数组，即结果数组cnt[l~r]+1。之后做完输入操作之后，求前缀和得到结果数组就好。代码如下：

#include 

using namespace std;

const int maxn=2e5+2;

int n,m,k;
int cnt[maxn],b[maxn];//结果数组，结果数组对应的差分数组

int main()
{
    cin>>n>>m>>k;
    int maxr=0;
    for(int i=0;i
        int t,c;
        cin>>t>>c;
        int l=t-c-k+1,r=t-k;//确定区间左端点与右端点
        maxr=max(maxr,r);
        //设结果对应的差分数组，用于对[l,r]做区间修改(cnt[l~r]+1,即覆盖该范围的区间个数+1，对应对b[l]+=1,b[r+1]-=1)
        b[max(1,l)]+=1;//因为l可能为非正数，此时该区间覆盖的点最小显然可从1开始
        b[max(r,0)+1]-=1;//因为r可能为非正数，此时该区间覆盖的点最大显然可到1
    }
    for(int i=1;i<=maxr;i++)//对差分数组求前缀和得到结果数组
    {
        cnt[i]=cnt[i-1]+b[i];
    }
    for(int i=0;i
        int q;
        cin>>q;
        cout<