题目描述

难度分:$1200$

输入$T(\leq 5)$表示$T$组数据。

每组数据输入$n(1 \leq n \leq 10^5)$，$x(1 \leq x \leq 10^4)$和长为$n$的数组$a(0 \leq a[i] \leq 10^4)$。

输出$a$的最长连续子数组的长度，满足子数组的元素和不是$x$的倍数。

如果没有这样的子数组，输出$-1$。

输入样例

3
3 3
1 2 3
3 4
1 2 3
2 2
0 6

输出样例

2
3
-1

算法

同余+线段树

有一个比较无脑数据结构做法，我们可以遍历$a$数组维护在模$x$意义下的前缀和$sum=\Sigma_{j=1}^{i}a[j]$ $mod$ $x$。并且在一棵线段树$seg$上维护某个$sum$出现的最早位置，即$seg[sum]$。当遍历到$i$位置前缀和为$sum_i$时，在线段树上查询$\neq sum_i$的最小索引$j$，那么子数组$(j,i]$的累加和肯定不为$x$的倍数，同时也是以$a[i]$结尾满足要求的最长子数组。

在初始情况下$seg[0]=0$，其他位置都是正无穷，表示这些前缀和还未出现过。考虑到线段树的下标以$1$开始，所以前缀和$sum_i$都往右偏移一个单位。

复杂度分析

时间复杂度

遍历$a$的时间复杂度为$O(n)$，对每个$i$都有对线段树的查询和修改操作，时间复杂度为$O(log_2n)$，所以整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的数组$a$，空间瓶颈在于线段树，而线段树的值域和$x$相关，空间消耗是$O(x)$的。所以整个算法的额外空间复杂度为$O(x)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int T, n, x, a[N];

class SegmentTree {
public:
    struct Info {
        int l, r, v;
        Info() {}
        Info(int left, int right, int val): l(left), r(right), v(val) {}
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u] = Info(l, r, N);
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid + 1, r);
            pushup(u);
        }
    }

    void modify(int pos, int val) {
        modify(1, pos, val);
    }

    Info query(int l, int r) {
        if(l > r) return Info(0, 0, N);
        return query(1, l, r);
    }

private:
    void modify(int u, int pos, int val) {
        if(seg[u].l == pos && seg[u].r == pos) {
            seg[u] = Info(pos, pos, val);
        }else {
            int mid = seg[u].l + seg[u].r >> 1;
            if(pos <= mid) modify(u<<1, pos, val);
            else modify(u<<1|1, pos, val);
            pushup(u);
        }
    }

    Info query(int u, int l, int r) {
        if(l <= seg[u].l && seg[u].r <= r) return seg[u];
        int mid = seg[u].l + seg[u].r >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    void pushup(int u) {
        seg[u] = merge(seg[u<<1], seg[u<<1|1]);
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l;
        info.r = rchild.r;
        info.v = min(lchild.v, rchild.v);
        return info;
    }
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &x);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        SegmentTree seg;
        seg.build(1, 1, x);
        seg.modify(1, 0);
        vector<int> pre(x, -1);
        int ans = -1, sum = 0;
        pre[sum] = 0;
        for(int i = 1; i <= n; i++) {
            sum = (sum + a[i]) % x;
            int j = min(seg.query(1, sum).v, seg.query(sum + 2, x).v);
            ans = max(ans, i - j);
            if(pre[sum] == -1) {
                pre[sum] = i;
                seg.modify(sum + 1, i);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}