d这套题，考察模拟、遍历、数据结构和二分法。第一题比较简单，但是第二题纯模拟没办法拿到所有用例，需要设计合理的数据结构进行加速，拿满分有一定难度。
一、讨厌鬼的组合帖子
题目描述
讨厌鬼有 n 个帖子。第 i 个帖子的点赞数为 a[i] 点踩数为 b[i]。你可以选择任意个帖子组合起来。
组合帖子的点赞数和点踩数为所有被组合帖子点赞数和点踩数之和。已知一个帖子的点赞数为 x，点踩数为 y，则该帖子的吸引度为 |x - y|。讨厌鬼需要选择若干个帖子组合起来，使得这个组合帖子的吸引度尽可能大。请你告诉他这个吸引度最大是多少？
输入描述
第一行输入一个整数 n(1 <= n <= 10^5)。
第二行输入 n 个整数 a[i](1 <= a[i] <= 10^9)
第三行输入 n 个整数 b[i](1 <= b[i] <= 10^9)。
输出描述
一行一个整数，表示最大吸引度。
输入示例
4
4 2 1 1
2 1 4 4输出示例
6提示信息
选择第 3 个和第 4 个帖子组合后，点赞数为 2，点踩数为 8，吸引度为|2 - 8| = 6。
题目分析：
【题目类型：遍历】
先对两个数组求差，正数和负数分别求和，绝对值最大者就是答案。
代码：
n = int(input())
A = input().split()
B = input().split()
a = [int(i) for i in A ]
b = [int(i) for i in B ]pos = 0
neg = 0for i in range(n):temp = a[i]-b[i]if temp < 0:neg += tempelse:pos += temp
neg = abs(neg)
if neg > pos:print(neg)
else:print(pos)二、小红的第16版方案
题目描述
小红正在做一个计划，她先写了份初版方案，但是领导不太满意，让小红改一改。
改着改着，小红就改了 16 版方案，然后领导说，还是用初版方案吧，现在小红非常的.....
小红组内有 n 个人，大家合作完成了一个初版方案，初始时大家的愤怒值都是 0。
但是领导对方案并不满意，共需要修改 m 次方案，每次修改会先让第 l 到 r 个人的愤怒值加 1，然后再修改方案。
组内每个人都有一个愤怒阈值 a，一旦第 i 次修改时有人愤怒值大于愤怒闻值，他就会去找领导对线，直接将最终的方案定为第 i - 1 方案，并且接下来方案都不需要再修改了。
小红想知道，最终会使用第几版方案。初版方案被认为是第 0 版方案。
输入描述
第一行输入两个整数 n, m(1 <= n, m <= 10^5)表示数组长度和修改次数。
第二行输入 n 个整数表示数组a(0 <= a <= 10^9)
接下来 m 行，每行输入两个整数l, r(1 <= l <= r <= n)
输出描述
输出一个整数表示答案
输入示例
2 3
2 2
1 1
1 2
2 2输出示例
3提示信息
改为三次方案，大家的愤怒度都为 2，都不超过愤怒阈值，所以使用最后一版方案。
题目分析：
【题目类型：模拟，差分数组，二分查找】
但是模拟只能跑90%的用例。在模拟的过程中，对于m次操作，每一次我们需要检查l->r次，因此时间复杂度是O(mn)，在这个过程中更新数据和检查的过程是合并到一起的，我们没办法拆开处理。
对于区间的批量加减操作，我们可以引入差分数组，从而将该操作的时间复杂度从O(n)优化到O(1)。对于原始数组arr，我们计算其差分数组diff，diff[0]=arr[0]，i>0时，diff[i] = arr[i]-arr[i-1]。在对[l,r]区间执行批量+v操作时，只需要执行diff[l] += v 和 diff[r+1] -= v 即可。我们通过错位相加可以用O(n)的时间复杂度实现将diff复原回arr。
基于该数据结构，对于m次修改，我们可以实现O(m)时间复杂度的【更新】和O(n)时间复杂度的【查询】，因此可以将这两个过程拆分后分别处理，变为O(m+n)。这样可以实现对第m次的验证，由于怒意的增加是顺序递增的，因此我们可以使用二分法加速遍历1-m的过程，从O(m)优化位O(logm)，这样的综合时间复杂度就变为了O((m+n)logm)，优于O(mn)。
代码：
# 模拟，能拿90%的用例temp_in = input().split()
n, m = int(temp_in[0]), int(temp_in[1])
a = [int(i) for i in input().split()]ans = m
flag = True
for i in range(m):temp_in = input().split()l, r = int(temp_in[0])-1, int(temp_in[1])-1if flag:for j in range(l,r+1):a[j] -= 1if a[j] < 0:flag = Falseans = ibreakelse:breakprint(ans)temp_in = input().split()
n, m = int(temp_in[0]), int(temp_in[1])
a = [int(i) for i in input().split()]# 读取操作
operation = []
for i in range(m): # O(m)temp_in = input().split()l, r = int(temp_in[0])-1, int(temp_in[1])-1operation.append([l, r])# 更新到指定操作次数，并检查是否暴怒
def check(steps):# 构造差分数组 O(n)diff = [a[0]]for i in range(1, n): diff.append(a[i]-a[i-1])# 更新 O(m)for i in range(steps+1):l, r = operation[i][0], operation[i][1]diff[l] -= 1if r+1<n:diff[r+1] += 1# 检查 O(n)arr = [diff[0]]if arr[-1] < 0:return Falsefor i in range(1, n):arr.append(arr[-1]+diff[i])if arr[-1] < 0:return Falsereturn True# 二分法查找第一次暴怒的时刻
L, R = 0, m-1
ans = m
while L<=R: O(logm)Mid = (L+R)//2if check(Mid):L = Mid + 1else:ans = MidR = Mid - 1
print(ans)
