CSP-S 练习题：美丽的集合（ST表、二分查找、数论基础-GCD 的应用）

美丽的集合

题目描述

小 Q 喜欢美丽的集合，她认为的美丽的集合满足以下条件：这个集合的所有数字排序后为一段连续区间，比如 {6,2,5,3,4},{2,1}{6,2,5,3,4},{2,1}{6,2,5,3,4},{2,1} 是美丽的集合，{7,10}{7,10}{7,10} 不是美丽的集合。

小 Q 会施展魔法，每次魔法可以选中集合中的两个数 x≠yx
e yx=y，将 x+y2frac{x+y}{2}2x+y​ 塞进集合，（注意塞进的数要是正整数，否则不能塞进去），而通过若干次魔法可能可以让一个集合从不美丽变成美丽。

假如现在有一个序列 aaa，小 Q 首先会把序列中的所有元素塞进集合，再施展若干次魔法，希望这个集合能美丽。需要注意：如果一个相同的整数多次出现在序列中，小 Q 只会添加进集合一次。

小 Q 收到一个序列 {bn}{b_n}{bn​}，她现在想知道有多少个整数对 (l,r),1≤l≤r≤n(l,r),1le lle rle n(l,r),1≤l≤r≤n，满足子序列 bl∼rb_{lsim r}bl∼r​ 能被变成美丽的集合。

输入格式

第一行包含一个整数 nnn，表示序列的长度。

第二行有 nnn 个整数 a1∼ana_1sim a_na1​∼an​ 表示 {a}{a}{a} 中的元素。

输出格式

输出一行一个整数，表示满足条件的整数对的个数。

输入输出样例 #1

输入 #1

2
2 2

输出 #1

3

输入 #2

6
1 3 6 10 15 21

输出 #2

18

说明/提示

样例解释

第一个样例中有三个子序列，[2],[2],[2,2][2],[2],[2,2][2],[2],[2,2]。这些子序列都只包含一个整数 2，因此都是美丽的。

第二个样例中，考虑子序列 [3,6,10]→{3,6,8,10}→{3,6,7,8,10}→{3,5,6,7,8,10}→{3，4，5，6，7，8，9，10}[3,6,10] o {3,6,8,10} o {3,6,7,8,10} o {3,5,6,7,8,10} o {3，4，5，6，7，8，9，10}[3,6,10]→{3,6,8,10}→{3,6,7,8,10}→{3,5,6,7,8,10}→{3，4，5，6，7，8，9，10}，因此这个子序列是美丽的。

数据范围

对于全部的测试数据，满足 1≤n≤4×1051le nle 4 imes 10^51≤n≤4×105，1≤ai≤1091le a_ile 10^91≤ai​≤109。

参考代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn=4e5+10;
int t,n,Syt,m;
int a[maxn],b[maxn],lg[maxn];
int st[maxn][22];
inline void init(){
    lg[1]=0;
    for(int i=2;i<=4e5;i++)lg[i]=lg[i/2]+1;
}
inline void ipt(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    // sort(a+1,a+n+1);
    Syt=0;
    int x=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(x==a[i])++cnt;
        else {
            Syt+=cnt+cnt*(cnt-1)/2;
            x=a[i],cnt=1;
        }
    }
    Syt+=cnt+cnt*(cnt-1)/2;
    // printf("Syt = %lld
",Syt);
    for(int i=1;i<n;i++){
        int p=abs(a[i+1]-a[i]);
        while(p%2==0&&p)p/=2;
        if(p==1)++Syt;
    }
    // printf("Syt = %lld
",Syt);
    for(int i=1;i<n-1;i++){
        int p=abs(a[i+1]-a[i]),q=abs(a[i+2]-a[i+1]);
        b[i]=__gcd(p,q);
        while(b[i]%2==0&&b[i])b[i]/=2;
        st[i][0]=b[i];
    }
}
inline int gcd(int l,int r){
    int p=lg[r-l+1];
    return __gcd(st[l][p],st[r-(1<<p)+1][p]);
}
inline void ST(){
    m=n-2;
    for(int i=1;i<=lg[m];i++){
        for(int j=1;j<=m-(1<<i)+1;j++)st[j][i]=__gcd(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    }
}
inline void solve(){
    for(int i=1;i<=m;i++){
        if(gcd(i,m)!=1)break;
        int l=i,r=m,pos;
        while(l<=r){
            int mid=l+r>>1;
            if(gcd(i,mid)==1){
                pos=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        Syt+=m-pos+1;
    }
    printf("%lld
",Syt);
}
signed main(){
    init();
    t=1;
    while(t--){
        ipt();
        if(n==1){
            printf("1
");
            continue;
        }
        ST();
        solve();
    }
    return 0;
}