题解：AT_abc429_d [ABC429D] On AtCoder Conference

有一环，长为 $M$，有 $N$ 个人，第 $i$ 个人位于 $A_i$。给了个 $C(C\le N)$。这个环的坐标范围为 $0\sim M-1$。

定义 $X_i$ 为：从 $(i+0.5)$ 开始移动，遇到的人数达到或超过 $C$ 时遇到的人数。如果在结束的位置有多个人，那么这些人亦计入 $X_i$。

求 $\sum_{i=0}^{M-1} X_i$。

$M\le 10^{12}$。显然，真的照它题意求和，时间占用飞起。

注意到，任意的一对在 $[A_i,A_{i+1}]$ 范围内的整数 $i,j$，都满足 $X_i=X_j$。用这个性质来做。答案乘上区间之间的长度。

但它是个环。

因此需要做环上的特殊处理，比如 $[A_n,M-1]\cap[0,A_1-1]$ 这段区间需要格外处理。

再考虑怎么求，设现在位于 $x$，进行分类讨论：

那么求终止位置只需要二分即可。