题解 CF1730E Maximums and Minimums

· · 题解

考虑枚举最大值的位置 i，以及 a[i] 的一个因子 d 为区间最小值（先排除区间最小值等于最大值的情况，这个是容易计算的）。

为防止算重，先定义：

则计数 “区间左端点在 [P[i]+1,i] 中，右端点在 [i,S[i]-1] 中，区间 \min=d 的区间个数”。

记 l=P[i]+1，r=S[i]-1。

找到 i 前第一个 d 的位置 L，i 后第一个 d 的位置 R。

再求出：

那么：

然后分三种情况讨论

第一种，L,R 都合法，左右的 d 都取：

(L-\max(l,pre[L]+1)+1)\cdot(\min(r,suf[R]-1)-R+1)

第二种，L 合法，只取左边的 d：

(L-\max(l,pre[L]+1)+1)\cdot (\min(r,R-1,suf[L]-1)-i+1)

第三种，R 合法，只取右边的 d：

(i-\max(l,L+1,pre[R]+1)+1)\cdot (\min(r,suf[R]-1)-R+1)

全部加起来即可。

总复杂度为 O(A\ln A+\sum nD)，其中 A 为值域， D 为最大因子个数，10^6 内为 240。

前面的 P[],S[],pre[],suf[] 都可以用单调栈线性求出，i 左右第一个 d 的位置可以拿 vector 直接存。

具体见代码，还是比较简短的。

const int N=1e6+5;
int Head[N],vet[N*15],Next[N*15];
int pre[N],suf[N],P[N],S[N],stk[N],a[N];
int T,n,lst,top,edgenum; long long ans;
vector<int> vecL[N],vecR[N];
void add(int u, int v){
    edgenum++;
    vet[edgenum]=v;
    Next[edgenum]=Head[u];
    Head[u]=edgenum;
}
char buf[1<<24],*iS=buf;
#define gc() (*iS++)
inline int read(){
    char ch=gc(); int x=0;
    while (!isdigit(ch)) ch=gc();
    while (isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x;
}
int main(){
    for (int i=1; i<=1000000; i++)
        for (int j=i*2; j<=1000000; j+=i) add(j,i);
    fread(buf,1,1<<24,stdin);
    for (T=read(); T; T--){
        n=read(); lst=ans=0;
        for (int i=1; i<=n; i++){
            a[i]=read();
            if (a[i]!=a[i-1]) lst=i;
            ans+=i-lst+1;
        }
        stk[top=0]= 0 ; for (int i=1; i<=n; i++){ while (top && a[stk[top]]>=a[i]) top--; pre[i]=stk[top]; stk[++top]=i; }
        stk[top=0]=n+1; for (int i=n; i>=1; i--){ while (top && a[stk[top]]>=a[i]) top--; suf[i]=stk[top]; stk[++top]=i; }
        stk[top=0]= 0 ; for (int i=1; i<=n; i++){ while (top && a[stk[top]]< a[i]) top--;   P[i]=stk[top]; stk[++top]=i; }
        stk[top=0]=n+1; for (int i=n; i>=1; i--){ while (top && a[stk[top]]<=a[i]) top--;   S[i]=stk[top]; stk[++top]=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=P[i]+1,r=S[i]-1;
            for (int e=Head[a[i]]; e; e=Next[e]){
                int d=vet[e];
                int L=vecL[d].empty()?l-1:vecL[d].back(); if (suf[L]<i) L=l-1;
                int R=vecR[d].empty()?r+1:vecR[d].back(); if (pre[R]>i) R=r+1;
                if (L<l && R>r) continue;
                if (L>=l && R<=r) ans+=1ll*(L-max(l,pre[L]+1)+1)*(min(r,suf[R]-1)-R+1);
                if (L>=l) ans+=1ll*(L-max(l,pre[L]+1)+1)*(min(min(r,R-1),suf[L]-1)-i+1);
                if (R<=r) ans+=1ll*(i-max(max(l,L+1),pre[R]+1)+1)*(min(r,suf[R]-1)-R+1);
            }
            vecL[a[i]].push_back(i);
        }
        printf("%lld\n",ans);
        for (int i=1; i<=n; i++){
            pre[i]=suf[i]=P[i]=S[i]=0;
            vecL[a[i]].clear(),vecR[a[i]].clear();
        }
    }
}