D. Rain（思维/线性代数/差分数组）

题目 官方题解 很难、很有意思的一道题。

题意

给定n天，第i天降水在x[i]位置，降雨量为p[i]，与x[i]越远；当天，离x[i]位置越远，对应的降水量就越少。每远离x[i]一个单位的距离，降水量就减一。 即对于位置j，它在第i天，得到的降水量为max(0,p[i]-abs(x[i]-j))。

经过n天后，如果存在某个位置j，得到的总降水量，超过m，则说明位置j发生了洪水。

现在我们可以取消某一天i的降水，即可以将p[i]置为0。问是否还会发生洪水。

思路

一开始以为取中间的结点就可以，后来发现不对，忽略了max(0,…)这里的条件。

对于每次降水，它的影响范围为[x[i]-p[i], x[i]+p[i]]，且降水量随着离中心点x[i]降低。 如下图，黄色点为x[i]，降水量p[i]为紫色柱子。 本次降水影响范围为图中蓝色部分。 降水量与位置的关系，是一个线性方程，我们可以抽出三个位置坐标(x[i]-p[i],0) (x[i],p[i]),(x[i]+p[i],0)。进一步分析，前半段斜率为1，也就是说，从(x[i]-p[i],0)到(x[i],p[i])，降水量递增，我们可以将(x[i]-p[i],0)做为临界点，该点之后，斜率为1。类似的，在点(x[i],p[i])之后，斜率为-1。点(x[i]+p[i],0)之后，斜率为0。

我们将斜率的变动，用差值存储，那么有 (x[i]-p[i],1) (x[i],-2) (x[i]+p[i],1) 这里的是1，-2，1实际就是原来的增量1，-1，1存储的结果，为了方便计算我们用差分存储。

如何判断降水有没有超过m，只需要看超过m部分有没有降水量即可。

如何计算这n天中，降水超过m的部分？ 官方题解用得很巧妙，它维护了中点为x，平均降水量为h的降水阴影面积key

pll getIntersection(pll p1,pll p2)
{
	LL tx=max(p1.first+p1.second,p2.first+p2.second);
	LL ty=max(p1.second-p1.first,p2.second-p2.first);
	return {(tx-ty)/2,(tx+ty)/2};
}

计算出总的、超出m的降水运营面积后，怎么判断取消第i天，是否没有洪水？ 我们只需要看第i天的降水阴影面积，是否有覆盖全局的降水阴影面积，即可。

for (int i=1;ix[i]>>p[i];
		x[i]*=2;// 避开浮点数的运算
		p[i]*=2;// 避开浮点数的运算
		// 将所有的降雨的转折点存储在数组中
		// second表示 的是 "降雨净增量" ，这里用了差分思想 
		diff.push_back({x[i]-p[i],1});
		diff.push_back({x[i],-2});
		diff.push_back({x[i]+p[i],1});
	}
	sort(diff.begin(), diff.end());
	// a记录的是 当前位置的降雨量
	// d记录的是 当前位置的 降雨增量 ，也就是图里边的 "斜率"
	LL a=0,d=0;
	LL lst=0;// 上个结点位置 
	for (auto p:diff)
	{
		if (p.first!=lst)
		{
			// 新增的降雨量，图中的三角形面积
			// 由于前面m已经 乘2，这里 (p.first-lst)*d不需要 除2 
			a=a+(p.first-lst)*d; 
			lst=p.first;
			if (a>m)// 更新全局的、超出m 的降水量 
				key=getIntersection(key,{p.first,a-m});
		}
		d+=p.second;//  更新 "斜率" 
	}
	for (int i=1;i