hdu 5288 OO’s Sequence 枚举+二分

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define LL long long
#define pb push_back

using namespace std;

const int maxn=1e5+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;

int a[maxn];
int l[maxn];
int r[maxn];
vector <int> di[maxn];
vector <int> pos[maxn];

void pre_init()
{
    for(int i=1;i<maxn;i++){
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                di[i].pb(j);
                if(i/j != j)
                    di[i].pb(i/j);
            }
        }
    }
}

void init(int n)
{
    for(int i=1;i<maxn;i++){
        pos[i].clear();
    }
}

void solve(int );

int main()
{
    pre_init();

    int n;
    while(~scanf("%d",&n)){
        init(n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            pos[a[i]].pb(i);
        }
        solve(n);
    }
    return 0;
}

void solve(int n)
{
    for(int i=1;i<=n;i++){
        l[i]=1,r[i]=n;
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<di[a[i]].size();j++){
            int k=di[a[i]][j];

            int left=0,right=pos[k].size()-1;

            if(right<left)
                continue;

            if(pos[k][left]<i){
                while(right-left>1){
                    int mid=(left+right)>>1;
                    if(pos[k][mid]>=i)
                        right=mid;
                    else
                        left=mid;
                }
                if(pos[k][right]<i)
                    l[i]=max(l[i],pos[k][right]+1);
                else
                    l[i]=max(l[i],pos[k][left]+1);
            }


            left=0,right=pos[k].size()-1;
            if(pos[k][right]>i){
                while(right-left>1){
                    int mid=(left+right)>>1;
                    if(pos[k][mid]<=i)
                        left=mid;
                    else
                        right=mid;
                }
                if(pos[k][left]>i)
                    r[i]=min(r[i],pos[k][left]-1);
                else
                    r[i]=min(r[i],pos[k][right]-1);
            }


        }
    }

    /*
    for(int i=1;i<=n;i++)
        printf("%d %d\n",l[i],r[i]);
    */

    LL ret=0;
    for(int i=1;i<=n;i++){
        ret+=(i-l[i]+1)*(r[i]-i+1)%mod;
        ret=(ret+mod)%mod;
    }


    printf("%I64d\n",ret);
    return ;
}