萌新刚学OI

思路：离散化后上树状数组，对于每个数分解质因数，对每个质因数开一个树状数组来记录这个质因数上的情况

code:

#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int total=1;
vector<int>OldToNew;
vector<pair<int,int>>sortVector;
void deal()
{
    sort(sortVector.begin(), sortVector.end());
    OldToNew.resize(sortVector.size());
    OldToNew[sortVector[0].second]=total;
    for (size_t i = 1; i < sortVector.size(); i++)
    {
        if (sortVector[i].first!=sortVector[i-1].first)
        {
            total++;
        }
        OldToNew[sortVector[i].second]=total;
    }
}
//----------------------------------------------------------------
vector<vector<int>>binaryTree;

inline int LowestBit(const int&n)
{
    return n&-n;
}
inline void AddData(int x,int y,const int&data)
{
    while(y<=total)
    {
        binaryTree[x][y]=max(binaryTree[x][y],data);
        y+=LowestBit(y);
    }
}
inline int Query(int x,int y)
{
    int ans=0;
    while(y>0)
    {
        ans=max(ans,binaryTree[x][y]);
        y-=LowestBit(y);
    }
    return ans;
}
//----------------------------------------------------------------
vector<int>prime;
vector<bool>isPrime;
vector<int>cntPrime;
void GetPrime(const int&maxn)
{
    isPrime.assign(maxn+1,true);
    for(int i=2;i<=maxn;i++)
    {
        if(isPrime[i])
        {
            prime.push_back(i);
        }
        for(int j=0;j<prime.size()&&i*prime[j]<=maxn&&i%prime[j];j++)
        {
            isPrime[i*prime[j]]=false;
        }
    }
    cntPrime.assign(prime.size(),0);
}
//----------------------------------------------------------------
vector<vector<int>>allFactors;
//----------------------------------------------------------------
int N,maxA;
vector<int>A;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    A.resize(N);
    allFactors.resize(N);
    for(int i=0;i<N;i++)
    {
        cin>>A[i];
        maxA=max(maxA,A[i]);
        sortVector.push_back({A[i],i});
    }
    GetPrime(sqrt(maxA)+1);
    deal();
    binaryTree.resize(prime.size());
    for(int i=0;i<N;i++)
    {
        allFactors[i].clear();
        for (size_t j = 0; j < prime.size() && prime[j]*prime[j]<=A[i]; j++)
        {
            if(A[i]%prime[j]==0)
            {
                allFactors[i].push_back(j);
                cntPrime[j]++;
                if(cntPrime[j]==2){
                    binaryTree[j].assign(total,-1);
                }
                while (A[i]%prime[j]==0)
                {
                    A[i]/=prime[j];
                }
            }
        }
        auto endPrime=lower_bound(prime.begin(),prime.end(),A[i]);
        if (endPrime!=prime.end()&&*endPrime==A[i])
        {
            cntPrime[endPrime-prime.begin()]++;
            if(cntPrime[endPrime-prime.begin()]==2){
                binaryTree[endPrime-prime.begin()].assign(total,-1);
            }
            allFactors[i].push_back(endPrime-prime.begin());
        }
    }
    for (auto &&i : allFactors[0])
    {
        if (cntPrime[i]>=2)
        {
            AddData(i,OldToNew[0],0);
        }
    }
    for(int i=1;i<N;i++)
    {
        bool found = false;
        int maxN = 0;
        for (auto &&j : allFactors[i])
        {
            if (cntPrime[j]>=2)
            {
                int maxBefore=Query(j,OldToNew[i]-1)+1;
                if (maxBefore>maxN)
                {
                    maxN=maxBefore;
                    found=true;
                }
            }
        }
        if (found&&i!=N-1)
        {
            for (auto &&j : allFactors[i+1])
            {
                if (cntPrime[j]>=2)
                {
                    AddData(j,OldToNew[i+1],maxN);
                }
            }
        }
        if (i==N-1)
        {
            cout<<(maxN==0?-1:maxN)<<endl;
            return 0;
        }
    }
    return 0;
}