自动搬运

查看原文

来自洛谷，原作者为

	Sea_Level 繁花似锦觅安宁，淡云流水度此生。

搬运于2025-08-24 21:41:33，当前版本为作者最后更新于2020-03-11 18:05:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 P2781 【传教】

题意很明了，我就不多说了。这道题的难点在于如何累加。由于数据范围很大，所以我们可以先把l,r,k都存下来等到询问的时候再计算。

首先我们先把简单的（传教时的操作）写出来，代码就不放了。

好了，接下来就是计算询问的结果（询问，重点）

如果一段区间在l~r，那么就将其间的所有元素都加上k。由此我们得到式子：

$ans+=(long long)k[j]*(min(rx,r[j])-max(lx,l[j])+1)$

解释：这里还要判断只有一部分重叠的情况，如果两段区间不是完全重合的那就取重合的部分，尾部肯定要取最小，头部肯定要取最大。如果是完全重合这段代码也适用。这里要强制转换成long long。

完整代码：

#include<iostream>
using namespace std;
int n,m,l[1010],r[1010],k[1010],cnt=0,f=0;//l，r，k3个数组是题目中所说的传教的范围和增加的信仰值，cnt是l,r,k3个数组的下标，f是判断是传教还是询问。
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>f;
		long long ans=0;//和，记得开long long
		if(f==1){//如果是传教
			cnt++;
			cin>>l[cnt]>>r[cnt]>>k[cnt];//这里不能直接用i，因为f可能是2，就会出错
		}else{//如果不是传教，是询问
			int lx,rx;//询问区间的头和尾
			cin>>lx>>rx;
			for(int j=1;j<=cnt;j++){
				if(lx<=r[j]&&rx>=l[j]){//如果有重叠
					ans+=(long long)k[j]*(min(rx,r[j])-max(lx,l[j])+1);//累加，记得强制转换成long long，不然只有80分
				}
			}
			cout<<ans<<endl;
		}
	}
	return 0;//拜拜！
}