自动搬运

查看原文

来自洛谷，原作者为

	Spasmodic 182375

搬运于2025-08-24 22:33:17，当前版本为作者最后更新于2022-02-19 10:03:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

666 AC。

考虑一个显然的 dp：

直接写是 $O(n^2\log v)$ 的，显然会 t。

考虑对其进行优化，我们可以枚举 $p|a_i$，然后就转化为

考虑后面这个式子，明显可以用权值线段树做，对 $a$ 离散化的话查询是 $O(\log n)$。

那么我们对于每个质因子，维护一颗权值线段树，并且每次计算完 $f_{i-1}$ 后，枚举 $p|a_i$ 在 $p$ 对应的权值线段树上在 $a_i$ 处更新 $f_{i-1}$。注意到每次更新的时候其实只有 $O(\log n)$ 个结点受到影响，那么采用动态开点线段树就可以把空间控制在 $O(n\omega(v)\log n)$，其中 $\omega(n)$ 表示 $n$ 的不同质因子数。

最后对于质因子分解，我们考虑一个简单的优化，在暴力分解的基础上线性筛出质数，然后试除法就可以只用 $\sqrt v$ 以内的质因子去试，这样复杂度可以少一个 $\log v$。

这样一来时间复杂度就是 $O(n\pi(\sqrt v)+n\omega(v)\log n)$，空间是 $O(n\omega(v)\log n)$，轻松通过。

// Problem: P7810 [JRKSJ R2] Upper
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7810?contestId=48251
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define endl '\n' 
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int P=998244353;
void chkmax(int &x,int y){if(x<y)x=y;}
void chkmin(int &x,int y){if(x>y)x=y;}
int qpow(int a,int k){
	int ret=1;
	while(k){
		if(k&1)ret=ret*(long long)a%P;
		a=a*(long long)a%P;
		k>>=1;
	}
	return ret;
}
int qpow(int a,int k,int p){
	int ret=1;
	while(k){
		if(k&1)ret=ret*(long long)a%p;
		a=a*(long long)a%p;
		k>>=1;
	}
	return ret;
}
int norm(int x){return x>=P?x-P:x;}
int reduce(int x){return x<0?x+P:x;}
void add(int&x,int y){if((x+=y)>=P)x-=P;}
struct IO_Tp {
    const static int _I_Buffer_Size = 2 << 22;
    char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer, *_I_end= _I_Buffer + _I_Buffer_Size;

    const static int _O_Buffer_Size = 2 << 22;
    char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;

    IO_Tp() { fread(_I_Buffer, 1, _I_Buffer_Size, stdin); }
    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    IO_Tp &operator>>(int &res) {
    	int f=1;
        while (_I_pos!=_I_end&&!isdigit(*_I_pos)&&(*_I_pos)!='-') ++_I_pos;
        assert(_I_pos!=_I_end);
        if(*_I_pos=='-')f=-1,++_I_pos;
        res = *_I_pos++ - '0';
        while (_I_pos!=_I_end&&isdigit(*_I_pos)) res = res * 10 + (*_I_pos++ - '0');
        res*=f;
        assert(_I_pos!=_I_end);
        return *this;
    }
    
    IO_Tp &operator>>(string &res){
    	res="";
    	auto blank=[&](char ch){
    		if(ch==' '||ch=='\n'||ch=='\r'||ch=='	'||ch=='\0')return 1;
    		return 0;
		};
		while(_I_pos!=_I_end&&blank(*_I_pos)) ++_I_pos;
    	while (_I_pos!=_I_end&&!blank(*_I_pos))res += *_I_pos++;
    	assert(_I_pos!=_I_end);
    	return *this;
	} 

    IO_Tp &operator<<(int n) {
    	if(n<0)*_O_pos++='-',n=-n;
        static char _buf[10];
        char *_pos = _buf;
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf) *_O_pos++ = *--_pos;
        return *this;
    }

    IO_Tp &operator<<(char ch) {
        *_O_pos++ = ch;
        return *this;
    }
    
    IO_Tp &operator<<(string &res){
    	for (char ch:res) *_O_pos++ = ch;
    	return *this;
	} 
} IO;
const int N=1e5+5;
int n,m,a[N],sa[N],ua[N],f[N],cnt[N],pr[N][10];
int cp,p[N];
bool vst[N];
void init(int n){
	rep(i,2,n){
		if(!vst[i])p[++cp]=i;
		for(int j=1;j<=cp&&i*p[j]<=n;j++){
			vst[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
}
void dcp(int id){
	int x=a[id];
	for(int i=1;p[i]*p[i]<=x;i++)if(x%p[i]==0){
		pr[id][++cnt[id]]=p[i];
		while(x%p[i]==0)x/=p[i];
	}
	if(x>1)pr[id][++cnt[id]]=x;
}
unordered_map<int,int>rt;
int tot;
struct node{
	int lc,rc,ma;
}st[N<<5];
void pushup(int k){st[k].ma=max(st[st[k].lc].ma,st[st[k].rc].ma);}
void insert(int&k,int l,int r,int p,int v){
	if(!k)k=++tot;
	if(l==r)return chkmax(st[k].ma,v),void();
	int mid=l+r>>1;
	if(p<=mid)insert(st[k].lc,l,mid,p,v);
	else insert(st[k].rc,mid+1,r,p,v);
	pushup(k);
	return;
}
int ask(int p,int l,int r,int x,int y){
	if(!p)return -2;
	if(x<=l&&r<=y)return st[p].ma;
	int mid=l+r>>1,ret=-2;
	if(x<=mid)chkmax(ret,ask(st[p].lc,l,mid,x,y));
	if(mid<y)chkmax(ret,ask(st[p].rc,mid+1,r,x,y));
	return ret;
}
int main(){
	IO>>n;
	init(1e5);
	rep(i,1,n)IO>>a[i],sa[i]=a[i],dcp(i);
	sort(sa+1,sa+n+1);
	m=unique(sa+1,sa+n+1)-sa-1;
	rep(i,1,n)ua[i]=lower_bound(sa+1,sa+m+1,a[i])-sa;
	memset(f,-1,sizeof f);
	f[0]=0;
	rep(i,1,n){
		rep(j,1,cnt[i]){
			int p=rt[pr[i][j]];
			chkmax(f[i],ask(p,1,m,1,ua[i]-1)+1);
			if(f[i-1]>=0)insert(p,1,m,ua[i],f[i-1]);
			rt[pr[i][j]]=p;
		}
	}
	IO<<f[n]<<endl;
	return 0;
}