P15743题解
作者：WHAT_ARE_YOU_DOING(洛谷UID:1908713)
未经允许，禁止发布在任何平台。
Apple_pieYES (洛谷Uid:1412516) 可以使用
此图为证
本题使用到了两个算法：
差分和前缀和
这两个算法可以说是一对兄弟，十分相似，也经常用到，我先讲前缀和吧。
前缀和：
有一个数组sum={5,7,2,9,3}sum = \{5,7,2,9,3\}sum={5,7,2,9,3}，我们要求出 sum[2]∽sum[4]sum[2] \backsim sum[4]sum[2]∽sum[4]的和，我们可以这样写：
cpp
这样子写虽然方便，但是如果要执行10510^5105次求和、10610^6106次求和，甚至是10910^9109次求和，弊端这不就出来了吗？？？为了我们的代码运行时间更加的快，我们可以使用前缀和。
使用前缀和要定义一个数组，这个数组我们把他叫作 "ansansans"，ans[i]ans[i]ans[i]表示sum[0]∽sum[i]sum[0] \backsim sum[i]sum[0]∽sum[i]的和，即
{ans[0]=sum[0]ans[i]=sum[i]+ans[i−1] \begin{cases} ans[0] = sum[0] \\ ans[i] = sum[i]+ans[i-1]\\ \end{cases} {ans[0]=sum[0]ans[i]=sum[i]+ans[i−1]
这时候，有的同学就要问了：“前缀和有什么用呢，与求和有什么关系吗？”
问得好！奖励一朵小红花。
回到我们最开始的问题，我们可以把求sum[2]∽sum[4]sum[2] \backsim sum[4]sum[2]∽sum[4]的和的问题转化一下，可以变成求 (sum[0]∽sum[4])−(sum[0]∽sum[1])(sum[0] \backsim sum[4])-(sum[0] \backsim sum[1])(sum[0]∽sum[4])−(sum[0]∽sum[1]) 的值，简化了以后，也就是 sum[2]+sum[3]+sum[4]sum[2]+sum[3]+sum[4]sum[2]+sum[3]+sum[4] 的和。
而我们已经求出了 sum[0]∽sum[4]sum[0] \backsim sum[4]sum[0]∽sum[4] 和 sum[0]∽sum[1]sum[0] \backsim sum[1]sum[0]∽sum[1]的值。分别储存在了 ans[1]ans[1]ans[1] 和 ans[4]ans[4]ans[4] 里了，直接访问就可以了。
于是，我们可以写出如下代码：
cpp
这时，有同学又要问了：“如果题目给我们一个前缀和数组，让我们求原数组，我们要怎么办呢？”
真棒！再奖励一朵小红花。
这时候，就到了差分出场了。
差分：
差分是前缀和的逆运算，前缀和是加，而差分是减，比如这个前缀和数组 sum={5,12,14,23,26}sum=\{5,12,14,23,26\}sum={5,12,14,23,26}
使用查分前也要定义一个数组，这个数组我们把他叫作 "ansansans"，ans[i]ans[i]ans[i]表示数组原来的值，即
{ans[0]=sum[0]ans[i]=sum[i]−sum[i−1] \begin{cases} ans[0] = sum[0] \\ ans[i] = sum[i]-sum[i-1]\\ \end{cases} {ans[0]=sum[0]ans[i]=sum[i]−sum[i−1]
把我们之前的代码改一下，我们可以写出如下代码：
cpp
输出：
与前缀和不同的是：前缀和可以在原数组上做出更改，但是差分不可以在原数组上更改，运行下面的两个代码就可以知道了。
代码如下(CPP)
前缀和代码
输出：
差分代码
输出：
而正确的输出是：
所以，我们在使用差分时要注意哦！！！
这时有同学提问了：“差分又有什么用呢？”
你真是太棒了！奖励一朵小黄花！！！
我们新建一个数组 ans[5]ans[5]ans[5]，把 ansansans 清000，然后我们把ans[0]ans[0]ans[0] 加111。
这个时候，数组ansansans为：
而这个数组的前缀和数组为：
我们只用把ans[i]ans[i]ans[i]加111,ans[i]ans[i]ans[i]后面的所有值也都自动加111了。
所以：
把ans[i]ans[i]ans[i]加222,ans[i]ans[i]ans[i]后面的所有值也都自动加222了;
把ans[i]ans[i]ans[i]减111,ans[i]ans[i]ans[i]后面的所有值也都自动减111了。
我们再把ans[3]ans[3]ans[3]减去111，这时候，前缀和数组变为：
利用这个性质，我们就可以解决这道题了。
题目传送门
因为怪物会经过每一个格子，所以我们先计算出经过每一个格子，怪物会受到的伤害总数。
因为怪物在士兵的攻击范围内，都会受到111点伤害，所以我们用一个初始值全部为零的数组ansansans存伤害，每次输入两个数（LiL_iLi 和RiR_iRi ）时，我们将ans[Li]+1ans[L_i]+1ans[Li ]+1，ans[Ri+1]−1ans[R_i+1]-1ans[Ri +1]−1，在输入完成后，我们只用算一下前缀和，就可以得出怪物经过每一个格子所受到的伤害了。
剩下的代码，我相信你们会写。
对了，我要提醒一句：
十年ＯＩ一场空，不开LONG LONG 见祖宗
话不多说，上代码：
谢谢参考题解，如果有建议，欢迎各位大佬提出！！！
广告：
我的洛谷团队
