题目描述

难度分:$2700$

输入$T(\leq 10)$表示$T$组数据。所有数据的$n$之和$\leq 5 \times 10^5$。

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

输出$a$有多少个非空连续子数组$b$，满足$max(b)$是$min(b)$的倍数。

输入样例

6
1
1
2
2 4
2
2 3
4
2 4 7 14
7
16 5 18 7 7 12 14
6
16 14 2 6 16 2

输出样例

1
3
2
7
10
19

算法

单调栈+数论

首先，这个题使用完单调栈之后的分析和实现难度比较大。其次，这个题比较吃经验，不然估计不好时间复杂度根本不敢动手。

预处理

题目提到子数组要以某个值为最值，因此可以比较容易想到单调栈，先跑$4$次单调栈做预处理，得到$pre\_ge$（为了避免重复统计，这里要取等号）、$pre\_lt$、$suf\_gt$、$suf\_lt$这$4$个数组。其中$pre\_ge[i]$、$pre\_lt$、$suf\_gt$、$suf\_lt$分别表示$a[i]$左边大于等于自己、小于自己、右边大于自己、小于自己的最近位置。

有了这$4$个数组就可以枚举子数组的最大值$a[i]$，当$a[i]$要作为子数组的最大值时，那这个子数组的左边界$l$就应该在区间$(pre\_ge[i],i]$之内，右边界$r$就应该在区间$[i,suf\_gt[i])$之内。此时就能得到一个粗略的范围，但是还需要受到子数组最小值为$a[i]$的约数的限制。

枚举因子

对于$[1,10^6]$内的数字，因子的最大个数只有不超过$2^8$个，所以可以对每个$a[i]$枚举因子，时间复杂度也才$O(Dn)$（$D$为最大因子数量），在本题的数据量下是可以过的。

当遍历到$a[i]$枚举到它的因子$d$时，找到$i$前面最近$d$的位置$L$，$i$后面最近$d$的位置$R$。令$l=pre\_ge[i]+1$，$r=suf\_gt[i]-1$，如果出现以下两种情况，肯定就不合法了（因为$d$必须在区间$[l,r]$内）：

1. 若$L \lt l$或$suf\_lt[L] \lt i$，这时候$L$突破了$a[i]$为最大值时，左边界不能小于$l$的限制。且子数组内有比$d$更小的值，所以$d$不能成为最小值。
2. 若$R \gt r$或$pre\_lt[R] \gt i$，这时候$R$突破了$a[i]$为最大值时，右边界不能大于$r$的限制。且子数组内有比$d$更小的值，所以$d$不能成为最小值。

合法的情况有如下三种：

1. $L$和$R$都是合法的，$a[i]$和$d$分别为最大值和最小值的子数组有$(L-max(l,pre\_lt[L]+1)+1) \times (min(r,suf\_lt[R]-1)-R+1)$个。
2. $L$是合法的，只取左边的$d$，$a[i]$和$d$分别为最大值和最小值的子数组有$(L-max(l,pre\_lt[L]+1)+1) \times (min(r,R-1,suf\_lt[L]-1)-i+1)$个。
3. $R$是合法的，只取右边的$d$，$a[i]$和$d$分别为最大值和最小值的子数组有$(L-max(l,L+1,pre\_lt[R]+1)+1) \times (min(r,suf\_lt[R]-1)-R+1)$个。

$a[i]$对答案的贡献就是以上三种情况之和，最终答案就是所有$a[i]$的贡献。

复杂度分析

时间复杂度

分成以下几个部分讨论：

1. 遍历$a$数组统计答案时的时间复杂度为$O(Dn)$。
2. 单调栈预处理出$4$个前后缀的信息数组$pre\_ge$、$pre\_lt$、$suf\_lt$、$suf\_gt$，每个的时间复杂度都是$O(n)$，整体上还是$O(n)$的。
3. 而预处理每个数的因子时需要遍历$i \in [1,10^6]$，对于每个$i$，在$[1,A]$中它的倍数有$[\frac{A}{i}]$个（本题中$A=10^6$，其中$[.]$表示对$.$向下取整），因此$i$属于$[\frac{A}{i}]$个元素的因子。一共要遍历$\Sigma_{i=1}^{A}([\frac{A}{1}]+[\frac{A}{2}]+…+[\frac{A}{A}])=\Sigma_{i=1}^{A}A(1+\frac{1}{2}+…+\frac{1}{A})$次，根据调和级数的敛散性，这个时间复杂度为$O(AlnA)$。

综上，算法整体的时间复杂度为$O(AlnA+Dn)$。

空间复杂度

$4$个前后缀信息数组的空间是$O(n)$的；要存储每个数值的约数需要消耗的空间为$O(AlnA)$；还需要存储每个数值的索引列表$vecL$和$vecR$，由于最多$O(n)$个数值，一共存$O(n)$个索引，所以空间消耗为$O(n)$。

综上，算法整体的额外空间复杂度为$O(n+AlnA)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
#pragma GCC optimize(2)

using namespace std;
typedef long long LL;

const int N = 500010, M = 1000001;
vector<int> vecL[M], vecR[M], graph[M];
int T, n, a[N], pre_ge[N], suf_gt[N], pre_lt[N], suf_lt[N];
bool flag;

void add(int u, int v){
    graph[u].push_back(v);
}

void clear_env() {
    for(int i = 1; i <= n; i++) {
        vecL[a[i]].clear();
        vecR[a[i]].clear();
        pre_lt[i] = suf_lt[i] = pre_ge[i] = suf_gt[i] = 0;
    }
}

int main() {
    if(!flag) {
        for(int i = 1; i <= M - 1; i++) {
            for(int j = i*2; j <= M - 1; j += i) {
                add(j, i);
            }
        }
        flag = true;
    }
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        LL ans = 0, last = 0;
        // 读入数据的时候就把最大值等于最小值的段统计掉
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if(a[i] != a[i - 1]) last = i;
            ans += i - last + 1;
        }
        // 单调栈预处理
        stack<int> stk;
        // 前面比自己小的数的最近位置
        for(int i = 1; i <= n; i++) {
            while(stk.size() && a[stk.top()] >= a[i]) stk.pop();
            pre_lt[i] = stk.size()? stk.top(): 0;
            stk.push(i);
        }
        while(stk.size()) stk.pop();
        // 后面比自己小的数的最近位置
        for(int i = n; i >= 1; i--) {
            while(stk.size() && a[stk.top()] >= a[i]) stk.pop();
            suf_lt[i] = stk.size()? stk.top(): n + 1;
            stk.push(i);
        }
        while(stk.size()) stk.pop();
        // 前面小于等于自己的最近位置
        for(int i = 1; i <= n; i++) {
            while(stk.size() && a[stk.top()] < a[i]) stk.pop();
            pre_ge[i] = stk.size()? stk.top(): 0;
            stk.push(i);
        }
        while(stk.size()) stk.pop();
        // 后面大于自己的最近位置
        for(int i = n; i >= 1; i--) {
            while(stk.size() && a[stk.top()] <= a[i]) stk.pop();
            suf_gt[i] = stk.size()? stk.top(): n + 1;
            stk.push(i);
        }
        // 统计
        for(int i = n; i >= 1; i--) {
            vecR[a[i]].push_back(i);
        }
        for(int i = 1; i <= n; i++) {
            vecR[a[i]].pop_back();
            int l = pre_ge[i] + 1, r = suf_gt[i] - 1;
            for(int d: graph[a[i]]) {
                int L = vecL[d].empty()? l - 1: vecL[d].back();
                if(suf_lt[L] < i) L = l - 1;
                int R = vecR[d].empty()? r + 1: vecR[d].back();
                if(pre_lt[R] > i) R = r + 1;
                if(L < l && R > r) continue;
                if(L >= l && R <= r) ans += 1LL*(L - max(l, pre_lt[L] + 1) + 1) * (min(r, suf_lt[R] - 1) - R + 1);
                if(L >= l) ans += 1LL*(L - max(l, pre_lt[L] + 1) + 1)*(min(min(r, R - 1), suf_lt[L] - 1) - i + 1);
                if(R <= r) ans += 1LL*(i - max(max(l, L + 1), pre_lt[R] + 1) + 1) * (min(r, suf_lt[R] - 1) - R + 1);
            }
            vecL[a[i]].push_back(i);
        }
        printf("%lld\n", ans);
        clear_env();
    }
    return 0;
}