BZOJ-3509. [CodeChef] COUNTARI

给定一个长度为 n ~(1 \leq n \leq 10^5) 的数组 a_i~(0 \leq a_i \leq 3\cdot 10^4),问有多少对 (i, j, k) 满足 i < j < ka_i - a_j = a_j - a_k

也就是统计有多少对长度为 3 的等差子序列(题目连接 BZOJ-3509, CodeChef COUNTARI

例如 3 5 3 6 3 4 10 4 5 2,就有 (1, 3, 5), (1, 6, 9), (1, 8, 9), (3, 6, 9), (3, 8, 9), (5, 6, 9), (5, 8, 9), (4, 6, 10), (4, 8, 10) 一共 9 对

(more…)

Read More