前缀和与差分

叠干草

题目描述

有 $N$ （为奇数）堆干草，按 $1$~$N$ 编号，开始时每堆高度都是 $0$。
FJ给出 $K$ 条指令，每条指令包含两个用空格隔开的整数，例如 “$10$ $13$”，表示给 $10,11,12,13$ 这四堆干草分别叠加一捆干草，即高度均增加$1$。
FJ想知道，干草对完后，这 $N$ 堆干草高度的中位数是多少。

输入格式

第 $1$ 行：两个整数，分别是 $N$ 和 $K$。
第 $2$~$K+1$ 行：每行两个整数 $A$ 和 $B$（$1\le A\le B\le N$ ），表示一条指令。

输出格式

一个整数，表示中位数。

样例

样例输入

7 4
5 5
2 4
4 6
3 5

• 1
• 2
• 3
• 4
• 5

样例输出

1

• 1

样例解释

堆完后，高度分别是 $0,1,2,3,3,1,0$。排序后为 $0,0,1,1,2,3,3$，故中位数是 $1$。

数据范围与提示

对于 $100\%$ 的数据，$1\le N\le 10^6$，$1\le K\le 25000$

分析

如果对这道题采用模拟算法的话，那么会很慢。每一次你都需要对这个区间里的所有数全部进行加值处理，因此会超慢——以至于超时（TLE）所以我们需要优化。
乐迪加速！
咳，应该是那个差分。
为什么选择差分？
你看：
在第一次操作前：

0 0 0 0 0 0 0

• 1

差:

(0) 0 0 0 0 0 0

• 1

操作开始!

0 0 0 0 1 0 0
(0) 0 0 0 -1 1 0

0 1 1 1 1 0 0
(0) -1 0 0 0 1 0

0 1 1 2 2 1 0
(0) -1 0 -1 0 1 0

0 1 2 3 3 1 0
(0) -1 -1 -1 0 1 0

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

有没有发现什么？

假设现在的数组为:a b c d e f g，若使[c,f]区间每个值加1。
再假设差分数组为:a A B C D E F(a=a,A=a-b,B=b-c,C=c-d,D=d-e,E=e-f,F=f-g)
区间加完后成为：a b c+1 d+1 e+1 f+1 g
此时差分数组为:a A B-1 C D E F+1
那么不难发现：在区间的左端点——c处的差值减少1，f+1处差值增加1。由于我们记录了数组第1个数a，那我们就能根据差分数组求出当前数组的所有数。
接着排序求出中位数即可。

for (i = 0; i < m; i++) {
    scanf("%lld %lld", &l, &r);
    sum[l] -= 1;
    sum[r + 1] += 1;
}
a[1] = sum[1];//第一堆草堆
for (i = 2; i <= n; i++) a[i] = a[i - 1] - sum[i];//求最后草堆高
sort(a, a + n + 1);//排序
printf("%lld", a[n / 2 + 1]);

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9