区间 题解

题意简述

求长度为 \(n\) 的序列 \(a\) 的最长连续子序列 \([l, r]\)，满足 \(\exists i \in [l, r], \gcd(a_l, \ldots, a_r) = a_i\)。

\(1 \leq n \leq 4 \times 10 ^ 6\)，\(1 \leq a_i \leq 10^{18}\)。

题目分析

根据 \(\gcd(a, b) = a\) 等价于 \(b \bmod a = 0\)，这个区间的限制等价于 \(\forall j \in [l, r], a_j \bmod a_i = 0\)。进而我们发现，可以在 \(a_i\) 处统计答案，将问题转化为两部分。即，我们需要求出 \(l_i\)，表示最小的位置，满足 \(\forall j \in [l_i, i], a_j \bmod a_i = 0\)，\(r_i\) 同理。

我们直接扫是 \(\Theta(n ^ 2)\) 的，看看有没有地方重复计算了。显然是有的，比如有个 \(k < j\)，并且 \(a_k \bmod a_j = 0\)，我们扫过 \(a_j \bmod a_i = 0\) 后，就不用去扫 \(a_k\) 了。于是，我们想到，可以直接从 \(l_j - 1\) 继续扫下去。这样的时间复杂度如何保证呢？考虑这个算法的本质，就是维护了一个栈，栈中相邻的都不能整除。当我们新加入一个 \(a_i\) 时，从 \(l_j - 1\) 继续扫下去，可以看做是弹栈，因为之后就不会访问到 \(j\) 了。所以，这样的时间复杂度是线性 \(\Theta(n)\) 的。

代码

#include <cstdio>

const int MAX = 1 << 28;
char buf[MAX], *p = buf;
#ifdef XuYueming
# define fread(_, __, ___, ____)
#else
# define getchar() *p++
#endif
#define isdigit(x) ('0' <= x && x <= '9')
#define __yzh__(x) for (; x isdigit(ch); ch = getchar())
template <typename T>
inline void read(T &x) {
    x = 0; char ch = getchar(); __yzh__(!);
    __yzh__( ) x = (x << 3) + (x << 1) + (ch ^ 48);
}

const int N = 4000010;

using lint = long long;

int n, ans, stack[N], *top = stack, L[N], *Li = L;
lint val[N];

signed main() {
    #ifndef XuYueming
    freopen("interval.in", "r", stdin);
    freopen("interval.out", "w", stdout);
    #endif
    fread(buf, 1, MAX, stdin);
    read(n);
    register int i;
    for (i = 1; i <= n; ++i) {
        read(val[i]);
        while (top != stack && val[*top] % val[i] == 0) --top;
        *++Li = *top + 1, *++top = i;
    }
    *(top = stack) = n + 1;
    for (i = n; i; --i) {
        while (top != stack && val[*top] % val[i] == 0) --top;
        if (*top - *Li > ans)
            ans = *top - *Li;
        *++top = i, --Li;
    }
    printf("%d", ans);
    return 0;
}