csp202203-2【出行计划】题解 差分+前缀和

已知在 t t t时刻完成核酸检测，等待核算报告需要 k k k天，某场所核算报告有效期为 c c c天，则在 [ t + k , t + k + c ) [t+k,t+k+c) [t+k,t+k+c)天之间去这个场所是可以的。
题目一开始给了等待核酸检测出报告的时间 k k k天，接下来给了很多对 ( t i , c i ) (t_{i},c_{i}) (ti​,ci​)( t t t表示某人去这个地方的时间， c c c表示这个地方承认的核酸检测天数)
再给出许多询问，每次询问是给定一个正数 q （ q > 0 ） q（q>0） q（q>0）， q q q的意义是做核酸的时间。
则可以得到如下方程：
q + k ≤ t ＜ q + k + c q+k≤t＜q+k+c q+k≤t＜q+k+c
q + k ≤ t ≤ q + k + c − 1 q+k≤t≤q+k+c-1 q+k≤t≤q+k+c−1
则 q q q的范围是： t + 1 − k − c ≤ q ≤ t − k t+1-k-c≤q≤t-k t+1−k−c≤q≤t−k

题目给了 n n n组 ( t i , c i ) (t_{i},c_{i}) (ti​,ci​)，相应的就有 n n n个区间 [ t + 1 − k − c , t − k ] [t+1-k-c,t-k] [t+1−k−c,t−k]
对于每个 q q q，要计算落在这 n n n个区间内的哪几个区间？
进一步可以转换为对于一个实数 q q q，它落在这 n n n个区间的哪几个中？
我们可以想象一个数轴，数轴上的每个点处的数是 0 0 0,只要被一个区间覆盖，覆盖到的地方就全部 + 1 +1 +1，这样处理这 n n n个区间，我们就得到了这n个区间在数轴上的叠加覆盖，数轴上的数是几，那它就在几个区间内。

• 怎么让区间 [ t i + 1 − k − c i , t i − k ] [t_{i}+1-k-c_{i},t_{i}-k] [ti​+1−k−ci​,ti​−k]内的数全部 + 1 +1 +1呢?
  可以先差分，再计算前缀和
  https://blog.csdn.net/weixin_45798993/article/details/122495960

特殊边界处理：

• 对一个区间来说，如果它的上界 ≤ 0 ≤0 ≤0,是没有意义的，要跳过处理。
• 对一个区间来说，如果它的下界小于1，也没有意义，因为q是整数，题目交代了＞0，所以最小值为1，因此在处理区间的时候，下界最小不能小于1

这题在交代输入格式的时候，说了“按时间顺序给出”，很多人就想当然的以为是二分了，其实不然，不要被题目所迷惑了。

#include
#include
#include
#include
#include
using namespace std;
const int N=2e5+10;
int n,m,k,t,c,q;
int cnt[N];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&t,&c);
		int x=t+1-k-c,y=t-k;
		if(y<=0) continue;  //上界不能小于0，不然没意义
		x=max(1,x);  //下界不能小于1，不然是没意义的
		//cout<
		scanf("%d",&q);   //O（1）的查询操作
		printf("%dn",cnt[q]);
	}
	return 0;
}