什么是差分数组

t = [0,1,2,3,4]
d = [0,1,1,1,1]

就是用前一个减去后一个得到的数组, 还原只用求前缀和就好了

为什么要用

要频繁的变换一个区间的值, 如要改一个区间的值, $[i,j]$ 都加 2, 那么 $d[i]$ +=2, $d[j+1]$ -= 2, 就可以了.

蓝桥杯第十五届 python 研究生组 D 题 (opens new window)

在库存管理系统中，跟踪和调节商品库存量是关键任务之一。

小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 1 至 n 。

初始时，每种商品的库存量均为 0 。

为了高效地监控和调整库存量，小蓝的管理团队设计了 m 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L,R] ）。

执行这些操作时，区间内每种商品的库存量都将增加 1 。

然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 0 。

对此，请你为管理团队计算出，每个操作未执行时，库存量为 0 的商品的种类数。

输入格式 第一行包含两个整数 n 和 m ，分别表示商品的种类数和操作的个数。

接下来的 m 行，每行包含两个整数 L 和 R ，表示一个操作涉及的商品区间。

输出格式 输出共 m 行，每行一个整数，第 i 行的整数表示如果不执行第 i 个操作，则最终库存量为 0 的商品种类数。

数据范围 对于 20% 的评测用例，1≤n,m≤5×103 ，1≤L≤R≤n 。 对于所有评测用例，1≤n,m≤3×105 ，1≤L≤R≤n 。

输入样例：

5 3
1 2
2 4
3 5

输出样例：

1
0
1

样例解释 考虑不执行每个操作时，其余操作对商品库存的综合影响：

• 不执行操作 1 ：剩余的操作是操作 2 （影响区间 [2,4] ）和操作 3 （影响区间 [3,5] ）。执行这两个操作后，商品库存序列变为 [0,1,2,2,1] 。在这种情况下，只有编号为 1 的商品的库存量为 0 。因此，库存量为 0 的商品种类数为 1 。

• 不执行操作 2 ：剩余的操作是操作 1 （影响区间 [1,2] ）和操作 3 （影响区间 [3,5] ）。执行这两个操作后，商品库存序列变为 [1,1,1,1,1] 。在这种情况下，所有商品的库存量都不为 0 。因此，库存量为 0 的商品种类数为 0 。

• 不执行操作 3 ：剩余的操作是操作 1 （影响区间 [1,2] ）和操作 2 （影响区间 [2,4] ）。执行这两个操作后，商品库存序列变为 [1,2,1,1,0] 。在这种情况下，只有编号为 5 的商品的库存量为 0 。因此，库存量为 0 的商品种类数为 1 。

解析

n,m=map(int,input().split())
t=[]
for i in range(m):
    L,R=map(int,input().split())
    t.append((L-1,R-1))

每次都是改变一个区间, 故用差分数组

 # 差分数组初始化
  dif = [0] * (n + 2)

  # 处理每个操作，更新差分数组
  for L, R in operations:
      dif[L] += 1
      dif[R + 1] -= 1

  # 计算最终库存量数组
  f = [0] * (n + 1)
  for i in range(1, n + 1):
      f[i] = f[i - 1] + dif[i]

统计最终情况下 库存为 1 和 0 的情况. 0 是最终结果, 1 才有可能会变 0

cnt1 = [0] * (n + 1)
for i in range(1, n + 1):
    cnt1[i] = cnt1[i - 1] + (1 if f[i] == 1 else 0)

# 统计总库存为 0 的商品数
cnt0 = sum(1 for x in f[1:] if x == 0)

1 是以前缀和统计的

结果为

result = []
for L, R in operations:
    # 区间内库存为 1 的商品数减少
    # 这个区间所有为 1 的为 0, 也就是 a[r]-a[l-1]
    reduced = cnt1[R] - cnt1[L - 1]
    result.append(cnt0 + reduced)

完整代码

n, m = map(int, input().split())
t = []
for i in range(m):
    l, r = map(int, input().split())
    t.append((l - 1, r - 1))

dif = [0] * (n + 1)
for l, r in t:
    dif[l] += 1
    dif[r + 1] -= 1
f = [0]
for i in dif:
    f.append(i + f[-1])
f = f[1:-1]
count1 = [0]
count0 = sum([i == 0 for i in f])
for i in f:
    count1.append(count1[-1] + (i == 1))
count1 = count1
for l, r in t:
    print( count0 + count1[r+1] - count1[l])