前缀和与差分
介绍前缀和、差分的概念与应用。
前缀和
对于给定的数列 A，前缀和数列 S 可以通过递推表示：
$$ S[i] = \sum_{j=1}^{i}{A[j]} $$
对于部分和，数列 A 的某个区间和可以通过前缀和相减表示：
$$ sum(l, r) = \sum_{i=l}^{r}{A[i] = S[r] - S[l - 1]} $$
高维前缀和可根据容斥原理推断。
A = list(range(1, 11))
S = [0] * (len(A) + 1)
for i in range(len(A)):
S[i + 1] = S[i] + A[i]
print(S)
# A[1] - A[10]
# S[r] - S[l - 1]
print(S[10] - S[0])
# 原地更新 从1开始索引
S = [0] + list(range(1, 11))
n = len(S)
for i in range(1, n):
S[i] += S[i - 1]
print(S)
# A[1] - A[10]
# S[r] - S[l - 1]
print(S[10] - S[0])
例题 AcWing99 激光炸弹
Description
一种新型的激光炸弹，可以摧毁一个边长为 R 的正方形内的所有的目标。现在地图上有 n(N<=10000)个目标，用整数 Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为 R 的正方形的边必须和 x，y 轴平行。若目标位于爆破正方形的边上，该目标将不会被摧毁。
Input
第一行输入正整数 N 和 R，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。
接下来 N 行，每行输入一组数据，每组数据包括三个整数 Xi,Yi,Wi，分别代表目标的 x 坐标，y 坐标和价值，数据用空格隔开。
Output
输出仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过 32767）。
Range
$0≤R≤10^9,
0<N≤10000,
0≤Xi,Yi≤5000,
0≤Wi≤1000$
Sample Input
2 1
0 0 1
1 1 1
Sample Output
1
N, R = map(int, input().split())
R = min(5001, R)
S = [[0] * 5010 for _ in range(5010)]
for _ in range(N):
x, y, w = map(int, input().split())
S[x + 1][y + 1] = w
for i in range(1, 5010):
for j in range(1, 5010):
S[i][j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]
ans = 0
for i in range(R, 5010):
for j in range(R, 5010):
ans = max(ans, S[i][j] - S[i - R][j] - S[i][j - R] + S[i - R][j - R])
print(ans)
差分
对于给定数列 A，差分数列 B 可以表示为：
$$ B[1] = A[1], B[i] = A[i] - A[i - 1] (2 \le i \le n) $$
前缀和与差分是互逆运算，差分序列 B 的前缀和序列就是原序列 A，前缀和序列 S 的差分序列也是原序列 A。
原序列[l, r]区间内所有数+d，其差分序列 B 的变化为$B_l$+d，$B_{r + 1}$-d，其余位置不变。
对于原序列的区间操作可以转化为对点操作，降低操作复杂度。
例题 AcWing100 增减序列
Description
给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
Input
第一行输入正整数 n。
接下来 n 行，每行输入一个整数，第 i+1 行的整数代表 ai。
Output
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
Range
$0<n≤105,
0≤ai<2147483648$
Sample Input
4
1
1
2
2
Sample Output
1
2
"""
差分解决一段区域同时增加或减少的问题
给区间[L，R]上都加上一个常数c，则b[L] += c , b[R + 1] -=c
求出a的差分序列b，其中b1 = a1,b(i) = a(i) - a(i - 1) (2 <= i <= n)。令b(n + 1) = 0，题目对序列a的操作，相当于每次可以选出b1,b2…b(n + 1)中的任意两个数，一个加1，另外一个减一。目标是把b2,b3,…bn变为全0。最终得到的数列a就是由 n 个 b1 构成的
任选两个数的方法可分为四类
1、2 <= i , j <=n（优先）
2、i = 1, 2 <=j <=n
3、2 <= i <= n , j = n + 1
4、i = 1, j = n + 1（没有意义）
设b2,b3....bn中正数总和为p，负数总和的绝对值为q。首先以正负数匹配的方式尽量执行1类操作，可执行min(p,q)次。剩余|p - q|个为匹对，每个可以选与b1或b(n + 1)匹配，即执行2 或 3 类操作，共需|p - q|次
综上所诉，最少操作次数为min(p,q) + |p - q| = max(p, q)。根据|p - q|次第2、3类操作的选择情况，能产生|p - q| + 1中不同的b1的值，即最终得到的序列a可能有|p - q| + 1 种
"""
n = int(input())
a = [0] * (n + 1)
d = [0] * (n + 2)
for i in range(1, n + 1):
a[i] = int(input())
d[i] = a[i] - a[i - 1]
p, q = 0, 0
for i in range(2, n + 2):
if d[i] > 0:
p += d[i]
if d[i] < 0:
q -= d[i]
# 更有技巧的
# p += max(0, d[i])
# q += max(0, -d[i])
# p = sum(x for x in d[2:] if x > 0)
# q = sum(abs(x) for x in d[2:] if x < 0)
print(max(p, q))
print(1 + abs(p - q))
例题 AcWing101 最高的牛
Description
有 N 头牛站成一行，被编队为 1、2、3…N，每头牛的身高都为整数。当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。
现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。
求每头牛的身高的最大可能值是多少。
Input
第一行输入整数 N,P,H,M，数据用空格隔开。
接下来 M 行，每行输出两个整数 A 和 B ，代表牛 A 和牛 B 可以相互看见，数据用空格隔开。
Output
一共输出 N 行数据，每行输出一个整数。
第 i 行输出的整数代表第 i 头牛可能的最大身高。
Range
$1≤N≤5000,
1≤H≤1000000,
1≤A,B≤10000,
0≤M≤10000$
Sample Input
9 3 5 5
1 3
5 3
4 3
3 7
9 8
Sample Output
5
4
5
3
4
4
5
5
5
Notice
此题中给出的关系对可能存在重复
"""
题目中说对于两头牛它们可以互相看见，说明两牛之间的牛的身高都比这两只低，因此根据最优的原则，我们可知中间的牛可以都比这两只小1即可 。
现在我们考虑关系会不会有交叉的情况。
假设i<j<k<l;存在关系ik和jl，因为存在关系ik，因此k的身高大于j，又因为存在jl，所以j的身高大于k，前后互相矛盾，因此不存在关系存在交叉的情况。
所以对于该问题，我们可以假设全部都是最高身高，然后每出现一对关系，就将他们之间的牛的身高全减1，因为涉及区间加减1，我们可以采用差分和前缀和的关系来解决该问题，具体实现看代码，注意关系判重。
"""
N, P, H, M = map(int, input().split())
d = [0] * (N + 5)
existed = set()
for _ in range(M):
A, B = map(int, input().split())
if A > B:
A, B = B, A
if (A, B) not in existed:
existed.add((A, B))
d[A + 1] -= 1
d[B] += 1
else:
continue
for i in range(N + 1):
d[i] += d[i - 1]
for i in range(1, N + 1):
print(d[i] + H)