6.2号上午是头条今年的AI Camp笔试题。一共两道，OI赛制，有部分分。

第一题

给出一个长度为 $n$ 的数组 $a_1, a_2, … a_n$，请找出所有连续区间中，区间和最大同时这个区间0的个数小于等于3个，输出这个区间和。

输入描述

第一行一个正整数 $n$，表示数组长度， $1 \le n \le 10^6$。
第二行 $n$ 个整数 $a_1, a_2, … a_n$，其中 $-10^9 \le a_1, a_2, … a_n \le 10^9$。

输出描述

输出一个数，表示最大的和。
注意结果会超出整型范围，需用 %lld 输出。

样例

输入

9
10 0 1 0 2 0 3 0 15

输出：

21

算法

(单调队列) $O(n)$

先求原数组的前缀和，令 $s[i] = \sum_{k=1}^ia_k$，然后区间 $a_j, a_{j+1}, … a_{i}$ 的和可以表示成 $s[i] - s[j-1]$。
当我们固定区间的右端点 $i$ 时，为了使区间和最大，我们就要找一个最小的 $s[j-1]$，且 $j$ 满足 $a_j, a_{j+1}, … a_{i}$ 中0的个数不大于3。

我们可以扫描整个数组，用两个指针 $i,j(j \le i)$ 维护一个窗口，满足 $a_j, a_{j+1}, … a_{i}$ 这段窗口中最多有3个0。然后对于每个 $i$，在窗口中找一个前缀和的最小值，$s[i]$ 与最小值的差就是以 $i$ 为右端点的和最大的区间。

剩下的问题就是如何动态求区间的最小值。由于区间的两个端点都是单调往后走的，所以可以用单调队列来解决。
队列从队尾到队首单调递增，每次枚举到 $s[i]$，时，将队首所有大于 $s[i]$ 的元素全都弹出，然后将 $s[i]$ 插入队首。被弹出队列的元素坐标比 $i$ 小，会比 $s[i]$ 更先从窗口出去，且值比 $s[i]$ 大，所以一定不会被用到，所以可以弹出。$s[i]$ 插入队首后，队列的单调性不变。
然后每次移动窗口左端点时，如果移除的元素跟队尾元素相等，则弹出队尾元素。
每次队尾元素，就是当前窗口的最小值。

时间复杂度分析：整个数组仅被扫描常数次，所以时间复杂度是 $O(n)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
LL a[N], q[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }

    int tt = 1, hh = 0;
    LL res = 0;
    q[++hh] = 0;
    for (int i = 1, j = 0, zero = 0; i <= n; i++)
    {
        // a[i]表示前缀和，此处判断原a[i]是否为0
        if (a[i] == a[i-1]) zero++;
        while (zero > 3)
        {
            if (a[j] == a[j + 1]) zero--;
            if (a[j] == q[tt]) tt++;
            j++;
        }
        res = max(res, a[i] - q[tt]);
        while (tt <= hh && q[hh] > a[i]) hh--;
        q[++hh] = a[i];
    }
    cout << res << endl;
    return 0;
}

第二题

给 $n$ 个实数 $a_1, a_2, … a_n$，要求计算这 $n$ 个数两两之间差的绝对值下取整后的和是多少。

输入描述

第一行为一个正整数 $n$ 和一个整数 $m$。接下来 $n$ 行，第 $i$ 行为一个整数 $b_i$，$a_i = b_i / m$。

$1 \le n \le 10^5$, $1 \le m \le 10^9$, $0 \le b_i \le 10^{18}$。

输出描述

一个数，表示结果。注意结果可能会超出int范围，需要用 %lld 输出。

样例

输入：

5 3
1 2 3 4 5

输出：

3

算法

（归并排序） $O(nlogn)$

首先我们将数组 $b[]$ 从小到大排序，做差时让坐标大的减去坐标小的，这样我们就可以去掉绝对值符号了。

然后我们将原问题分为两部分来做：

1. 先不考虑下取整，即先计算两两之差的和；
2. 把多加的数减去；

先来看第一部分，我们把排好序的数画在数轴上，两数之差就是数轴上对应的两点之间线段的长度，两两数之差的和就是所有点对之间的线段总长度。
我们可以挨个考虑每个区间：$[b_1, b_2]$，$[b_2, b_3]$, … $[b_{n-1}, b_n]$，看看每个区间被加了多少次。实际上，区间 $[b_i, b_{i+1}]$ 会被计算 $(i-1) * (n-i+1)$ 次。我们把每个小线段乘上被计算的次数再求和，就是第一部分的答案；

再来看第二部分，多加的数就是每个差对 $m$ 求余数的和。我们可以先求所有 $b_i$ 模 $m$ 的余数（这里要注意一下，C++中对负数取模会得到负余数，我们要把所有负余数变成正余数），然后所有两数($b_i, b_j, i \lt j$)之差可以分为两类：

1. $b_i \% m \le b_j \% m$，则两个余数可以直接减；
2. $b_i \% m \gt b_j \% m$，则 $b_j \% m - b_i \% m$ 后，需要加上 $m$；

这里类似于求逆序对，可以用归并排序来解决，每次递归时，先计算左右两部分内部的值，计算完后，左右两部分都会变为有序（从小到大排序），此时再计算左右两部分之间的值会比较方便：
用指针 $i$ 遍历第一个数组，同时维护一个指针 $j$，表示第二个数组中的分界点，将大于 $b_i$ 和 小于等于 $b_i$ 的数分为两部分，然后可以用前缀和分别计算与 $b_i$ 做差之后的余数。

时间复杂度分析：第一部分先用 sort 排序，然后线性扫描一遍，第二部分只有一遍归并排序，所以总时间复杂度是 $O(nlogn)$。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
LL b[N], s[N];

LL msort(int l, int r)
{
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = msort(l, mid) + msort(mid + 1, r);
    s[mid] = 0;
    for (int i = mid + 1; i <= r; i++)
        s[i] = s[i - 1] + b[i];
    for (int i = l, j = mid + 1; i <= mid; i++)
    {
        while (j <= r && b[j] < b[i]) j++;
        res += s[j - 1] - (j - 1 - mid) * (b[i] - m);
        res += (s[r] - s[j - 1]) - (r - j + 1) * b[i];
    }
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (b[i] < b[j]) s[k++] = b[i++];
        else s[k++] = b[j++];
    while (i <= mid) s[k++] = b[i++];
    while (j <= r) s[k++] = b[j++];
    for (i = l, j = 0; i <= r; i++, j++)
        b[i] = s[j];
    return res;
}


int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(b + 1, b + n + 1);
    LL res = 0;
    for (int i = 2; i <= n; i++)
        res += (b[i] - b[i - 1]) * (i-1) * (n-i+1);
    for (int i = 1; i <= n; i++)
    {
        b[i] %= m;
        if (b[i] < 0) b[i] += m;
    }
    res -= msort(1, n);
    cout << res / m << endl;
    return 0;
}