摘要
Title: 2041. 干草堆
Tag: 差分
Memory Limit: 64 MB
Time Limit: 1000 ms

2041. 干草堆

题意

贝茜对她最近在农场周围造成的一切恶作剧感到抱歉，她同意帮助农夫约翰把一批新到的干草捆堆起来。
开始时，共有 N 个空干草堆，编号 1∼N。
约翰给贝茜下达了 K 个指令，每条指令的格式为 A B，这意味着贝茜要在 A…B 范围内的每个干草堆的顶部添加一个新的干草捆。
例如，如果贝茜收到指令 10 13，则她应在干草堆 10,11,12,13 中各添加一个干草捆。
在贝茜完成了所有指令后，约翰想知道 N 个干草堆的中值高度——也就是说，如果干草堆按照高度从小到大排列，位于中间的干草堆的高度。
方便起见，N 一定是奇数，所以中间堆是唯一的。
请帮助贝茜确定约翰问题的答案。

思路

差分即可

后面的问题转换为了求第K大数

快速排序，桶排 O(n)
二分 O(nlogn)

代码

'''
Author: NEFU AB-IN
Date: 2022-01-16 21:49:26
FilePath: \ACM\Acwing\2041.py
LastEditTime: 2022-01-16 22:01:57
'''
N = int(1e6 + 10)
a = [0] * int(N)
b = [0] * int(N)

if __name__ == '__main__':
    n, k = map(int, input().split())
    for i in range(k):
        l, r = map(int, input().split())
        b[l] += 1
        b[r + 1] -= 1
    for i in range(1, n + 1):
        a[i] = a[i - 1] + b[i]

    a[1:n + 1] = sorted(a[1:n + 1])

    print(a[n // 2 + 1])