2020QAU校赛G题题解：施肥差分区间

施肥 题目描述: QAU是著名的农业大学，所以学校里的树很多。假设学校有n颗树,树按1~n编号排列。 一天，QAUer因为偷钓虹子湖的鱼被农学院的老师们抓住了,他惩罚QAUer为学校里的树施肥。老师们要求你去给给定区间的树施肥一次, 假设有m个老师，每个老师分别给定的施肥区间，并且要求你最后统计所有树的价值之和。我们规定单个树的价值等于树的编号乘以给它施肥的次数。如给第二颗树施肥三次,它的价值就是2 * 3 = 6。 QAUer算了很久,发现学校里的树太多了,他算不过来，请你编写程序帮他统计所有树的价值之和。 Input: 第一行输入二个数n，m代表树的总数目与有几位老师,接下来m行,每行输入两个数,代表第i位老师给定的区间。m <= n <= 2e5; Ouput: 输出1个数，代表在QAUer为每棵树施肥的之后,所有树的价值之和。 Sample input1 : 5 3 1 2 3 4 2 3 Sample output1 : 15 Sample input2 : 3 2 1 3 2 3 Sample output2 : 11

思路：

根据题意,我们可以知道每次都要对不同的区间进行修改操作,如果单纯暴力求解的话肯定会超时,所以想到差分区间,每次单点修改区间,最后求一下前缀和即可。同时注意数据范围,使用long long 数据类型防止爆int.

标程

#include<iostream> #define Maxn 200005 using namespace std; long long d[Maxn]; long long ans = 0; int main() { int n, m; cin >> n >> m; for(int i = 1;i <= m;i++) { int l, r; cin >> l >> r; d[l]++;d[r + 1]--; } for(int i = 1;i <= n;i++) d[i] += d[i - 1]; for(int i = 1;i <= n;i++) ans += i * d[i]; cout << ans << endl; return 0; }