# C

# 题目大意

一个盒子里有若干个 $L$ 长度的饼干，你现在摇晃一次杯子，每个饼干可能变成

$x$ 和 $L - x$ 长度的饼干
保持不变
问，对于最终的结果 $(a_1, \ldots, a_n)$ ，你的初始的 $L$ 都有多少种可能？

# 数据范围

$1 \le n \le 3 \times 10^5$
$1 \le a_i \le 10^9$

# 题解

先对 $A$ 从小到大排个序

这题的解题关键在于，必须且只能摇晃一次杯子，那么可能有以下几种情况

所有饼干都没碎
- $a_1 = \ldots = a_n$
所有饼干都碎了
- $n \mod 2 == 0$ ，只有可能碎成偶数
- $\forall i \le \frac{n}{2}, a_i + a_{n - i + 1} = k$ ， $k$ 是定值
有饼干碎了，有饼干没碎
- 只有可能 $a_n$ 作为没碎的，然后倒着找 $a_n \to a_r$ ，找到 $r$ 的最小值
- 那么剩下的 $a_1 \to a_{r - 1}$ 必然是和 2. 情况相同，两两配对的，且配对值为 $a_n$
  容易踩坑的地方是，如果是有的碎、有的没碎的情况，还需要特判一下， $r - 1$ 必须是 $\ge 0$ 的偶数，即必须有饼可断

Python

n = int(input())
a = [0] + list(map(int, input().split()))

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

res = set()

# 全断
if n % 2 == 0:
    num = a[1] + a[n]
    flag = True
    for i in range(2, n // 2 + 1):
        if a[i] + a[n - i + 1] != num:
            flag = False
            break
    
    if flag:    res.add(num)

# 有断有不断
num = a[n]
flag = True

r = n
while r >= 1 and a[r] == num:
    r -= 1

if r == 0:
    res.add(num)
else:
    if r % 2 == 0:
        for i in range(1, r):
            if a[i] == num: continue

            if a[i] + a[r - i + 1] != num:
                flag = False
                break
        if flag:
            res.add(num)

res = list(res)
res.sort()

for i in res:
    print(i, end = ' ')

# D

# 题目大意

~~高精度？~~， 差分
给定 $n$ 个数， $(a_1, \ldots, a_n)$
求 $\sum\limits_{i=1}^n \sum\limits_{j = 0}^{a_i - 1} 10^j$

# 数据范围

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 2 \times 10^5$

# 题解

差分计算累加的值，然后模拟高精度即可

python

MAXA = 2 * (10 ** 5) + 10
n = int(input())
a = [0] + list(map(int, input().split()))

maxx = 0
cf = [0] * MAXA

for i in range(1, n + 1):
    cf[1] += 1
    cf[a[i] + 1] -= 1
    maxx = max(maxx, a[i])

for i in range(1, MAXA):  cf[i] += cf[i - 1]

# print(cf[1 : maxx + 1])

res = []

sum = 0

for i in range(1, maxx + 1):
    sum += cf[i]
    res.append(sum % 10)
    sum //= 10
    
while sum != 0:
    res.append(sum % 10)
    sum //= 10


for i in range(len(res) - 1, -1, -1):  print(res[i], end = "")

# E

# 题目大意

给定 $N$ 个数， $A = (a_1, \ldots, a_n)$
请你统计满足一下条件的 $(L, R)$ 数量

$1 \le L \le R \le N$
在子序列 $(A_L, \ldots, A_R)$ 中，任意两个不同位置的元素之差的绝对值 $\ge D$ （注意， $L = R$ 时，直接统计答案）

# 数据范围

$2 \le N \le 4 \times 10^5$
$1 \le A_i, D \le 10^9$

# 题解

# 错解

第一发想的 双指针

Python

from math import fabs

n, d = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))

cnt, i, j = 0, 1, 1

while True:
    while i < j:
        if fabs(a[j] - a[i]) < d:   i += 1
        else:   break
    
    cnt += j - i + 1
    j += 1

    if j > n:   break

print(cnt)

贪心 ABC 差分

# C

# 题目大意

# 数据范围

# 题解

# D

# 题目大意

# 数据范围

# 题解

# E

# 题目大意

# 数据范围

# 题解

# 错解

ABC-443