数字对

题目描述

小 H 是个善于思考的学生, 现在她又在思考一个有关序列的问题.

她的面前浮现出一个长度为 n 的序列 {ai}, 她想找出一段区间 [L, R] (\(1 \leq L \leq R \leq n\)) . 这个特殊区间满足, 存在一个 k (\(L \leq k \leq R\)) , 并且对于任意的 i (\(L \leq i \leq R\)) ,\(a_i\) 都能 被 ak 整除. 这样的一个特殊区间 [L, R] 价值为\(R - L\). 小 H 想知道序列中所有特殊区间的最大价值是多少, 而有多少个这样的区间呢? 这些 区间又分别是哪些呢? 你能帮助她吧.

输入格式

第一行, 一个整数\(n\).

第二行,\(n\) 个整数, 代表\(a_i\).

输出格式

第一行两个整数, num 和 val, 表示价值最大的特殊区间的个数以及最大价值.

第二行 num 个整数, 按升序输出每个价值最大的特殊区间的 L.

样例输入 1

5
4 6 9 3 6

样例输出 1

1 3
2

样例输入 2

5
2 3 5 7 11

样例输出 2

5 0
1 2 3 4 5

数据范围

30%:\(1 \leq n \leq 30\),\(1 \leq a_i \leq 32\).

60%:\(1 \leq n \leq 3000\),\(1 \leq a_i \leq 1024\).

80%:\(1 \leq n \leq 300000\),\(1 \leq a_i \leq 1048576\).

100%:\(1 \leq n \leq 500000\),\(1 \leq a_i < 2^{31}\).

Explanation

看起来是一道很高大上的题目. 最开始蒟蒻我想要这样写:

对所有的序列都可以遍历它们, 求得最大公约数看是否能够满足条件. 这个算法的复杂度应该 是 \(O(n^3)\) 的.

然后是不是能优化一下呢~ 于是我们就可以用线段树 (线段树在 gcd 函数上是有可合并性的) 来优化一下, 复杂度是 \(O(n^2 \times log(n))\).

接着说其实每一次记一下前面的状态就可以不必用数据结构, 直接水一个复杂度是 \(O(n^2)\) 的暴力搜索, 其实就可以得到 60 分正解了.

随后我们需要将目标转向更高级的算法: 做法应该是要有复杂度 \(O(n \times log(n))\) 的. 这样就用上了 Sparse Table (一个不知道的东西, 之前别人在写这道题的时候我还在做 第一道题, 写了半天 Splay 没有过去, 所以没有看), 然后可以在一定时间内 AC.

刚才那个算法 @JerrySkywalker 已经过了, 但是这里还有一个玄学做法:

(先膜一发 @许益冰大神)

她是这样说的: 可以从左边扫一遍, 然后从右边扫一遍. 因为这些数有这样的性质: 如果能够 构成在 L 到 R 的区间内有至少一个最大公约数, 那么这个最大公约数一定是所有数之中最小的数 (即其他数都是它的倍数). 具体证明过程可以读者自行脑补.

然后确定了这些最小位置后打一些标记, 标记哪一些位置是最小的, 然后再扫一遍, 就是 一个很快的做法了.

大概证明了一下, 算法复杂度是 \(O(n)\) 的. @JerrySkywalker 坚持说还带一个指数, 但是 我表示 gcd 可以算作常数, 因为最大值固定 (手动滑稽). 但是回到家写了一个 Proof Of Concept 之后发现连个 gcd 的影子都没有调用到, 所以这个 log 也可以去掉了, 然后 就是一个纯正的 \(O(n)\)~

这种 玄学做法是可以 AC 的, 实测证明.

之后我有可能会补上一个 ST 表的代码 (或者不会, 要看心情).

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 500100;

int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y); }

int n;
int arr[maxn], flag[maxn];
int dis[maxn][2];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    // Scan the entire array with this nice scanning utility.
    for (int i = 1; i <= n; ) {
        dis[i][0] = 0;
        int j = i + 1;
        for (; j <= n; j++) {
            if (arr[j] % arr[i] != 0)
                break;
            dis[i][0]++;
        }
        flag[i] = i;
        for (int k = i; k < j - 1; k++) {
            dis[k + 1][0] = dis[k][0] - 1;
            flag[k + 1] = i;
        }
        i = j;
    }
    for (int i = n; i >= 1; ) {
        dis[i][1] = 0;
        int j = i - 1;
        for (; j >= 1; j--) {
            if (arr[j] % arr[i] != 0)
                break;
            dis[i][1]++;
        }
        flag[i] = i;
        for (int k = i; k > j + 1; k--) {
            dis[k - 1][1] = dis[k][1] - 1;
            flag[k - 1] = i;
        }
        i = j;
    }
    // Done scanning, now just processing the results.
    vector<int> vec;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int tmp = dis[i][0] + dis[i][1];
        // printf("i %d tmp %d\n", i, tmp);
        // // Deprecated judgement method... (Overridden by code block lower)
        // if (i > 1 && (dis[i][0] < dis[i - 1][0] || dis[i][1] > dis[i + 1][1]))
        //     continue;
        if (i != flag[i])
            continue;
        if (tmp < res) {
            continue;
        } else if (tmp == res) {
            vec.push_back(i - dis[i][1]);
        } else { // tmp > res
            vec.clear();
            vec.push_back(i - dis[i][1]);
            res = tmp;
        }
    }
    printf("%d %d\n", int(vec.size()), res);
    sort(vec.begin(), vec.end());
    for (unsigned int i = 0; i < vec.size(); i++)
        printf("%d ", vec[i]);
    return 0;
}