E题：O(n) 简洁写法

主要思路

考虑以 轴为矩形最右侧时，矩形最左侧的取值范围：

• 对于 轴方向长度 小于 轴方向长度的矩形，若矩形最左侧的合法范围为 ，那么应该有以下限制：
  
  对 ，此时矩形 轴方向长度为 ，那么 轴方向的方案数为 ，即 ，那么此时 位置对答案的贡献为：
  
  若 的线段数量为 ， 的线段下标累加和为 ，则贡献可简化为：
  
• 对于 轴方向长度 大于 轴方向长度的矩形，若矩形最左侧的合法范围为 ，那么应该有以下限制：
  
  对 ，此时矩形 轴方向长度为 ，那么 轴方向的方案数为 ，即 ，那么此时 位置对答案的贡献为：
  
  若 的线段数量为 ， 的线段下标累加和为 ，则贡献可简化为：
  

使用双指针即可维护 ，使用前缀和即可 得到 位置的贡献。

核心代码

int MAXN = 100000;

void solve() {
    int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
    long[] cnt = new long[MAXN + 1], sum = new long[MAXN + 1];
    for (int i = 0; i < n; i++) {
        cnt[sc.nextInt()] = 1;
    }
    long ans = 0;
    for (int i = 1, l1 = 1, r1 = 0, l2 = 1, r2 = 0; i <= MAXN; i++) {
        while (i - l1 + k > m) {
            l1++;
        }
        while (r1 + 1 < i && i - r1 + k > 1) {
            r1++;
        }
        while (i - l2 - k > m) {
            l2++;
        }
        while (r2 + 1 < i && i - r2 - k > 1) {
            r2++;
        }
        if (cnt[i] == 1) {
            sum[i] = i;
            if (l1 <= r1) {
                ans += (cnt[r1] - cnt[l1 - 1]) * (m - k - i + 1) + sum[r1] - sum[l1 - 1];
            }
            if (l2 <= r2) {
                ans += (cnt[r2] - cnt[l2 - 1]) * (m + k - i + 1) + sum[r2] - sum[l2 - 1];
            }
        }
        sum[i] += sum[i - 1];
        cnt[i] += cnt[i - 1];
    }
    out.println(ans);
}