[CF1603D] Artistic Partition——欧拉函数，线段树优化DP

问题其实就是要你把 1 ∼ n 1sim n 1∼n 分成 k k k 段，最小化每一段的 c c c 值的和。

首先我们会想到，如果区间 [ l , r ] [l,r] [l,r] 中不存在两个有倍数关系的数，即 r < 2 l r<2l r<2l，那么 c ( l , r ) c(l,r) c(l,r) 就会取最小值 r − l + 1 r-l+1 r−l+1。

也就是说，如果我们按 [ 1 , 1 ] , [ 2 , 3 ] , [ 4 , 7 ] , [ 8 , 15 ] . . . [1,1],[2,3],[4,7],[8,15]... [1,1],[2,3],[4,7],[8,15]... 这样的方式去分段，那么只需分 log ⁡ n log n logn 段即可把答案取到最小值 n n n，而且答案关于段数单调不增。

所以我们只需要考虑 k < log ⁡ n k

考虑设DP状态 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示把 1 ∼ i 1sim i 1∼i 分成 j j j 段时的最小答案，转移需要枚举分的最后一段是多少，复杂度不可通过。

考虑加速这个过程，观察式子：
c ( l , r ) = ∑ j = l r ∑ d ≥ l , d ∣ j ∑ i = 1 j d [ gcd ⁡ ( i , j d ) = 1 ] = ∑ j = l r ∑ d ≥ l , d ∣ j φ ( j d ) c(l,r)=sum_{j=l}^rsum_{dge l,d|j}sum_{i=1}^{frac{j}{d}}[gcd(i,frac{j}{d})=1]=sum_{j=l}^rsum_{dge l,d|j}varphi(frac{j}{d}) c(l,r)=j=l∑r​d≥l,d∣j∑​i=1∑dj​​[gcd(i,dj​)=1]=j=l∑r​d≥l,d∣j∑​φ(dj​)
我们可以想到用线段树维护最小的DP值，每次枚举 i i i 的因子然后用预处理出的欧拉函数做一个前缀加操作，查询就直接查前缀最小值即可。

这个做法的复杂度是 O ( n log ⁡ 3 n ) O(nlog^3n) O(nlog3n) 的，比正解多一个 l o g log log，但是zkw线段树随便过。

#include//JZM yyds!!
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
#define END putchar('n')
using namespace std;
const int MAXN=100002;
const ll INF=1e18;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
inline void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
inline ll lowbit(ll x){return x&-x;}

bool nop[MAXN];
int pr[MAXN],le,phi[MAXN];
inline void init(int n){
	nop[0]=nop[1]=1,phi[1]=1,le=0;
	for(int a=2;a<=n;a++){
		if(!nop[a])pr[++le]=a,phi[a]=a-1;
		for(int i=1,u;i<=le&&(u=pr[i]*a)<=n;i++){
			nop[u]=1;
			if(a%pr[i]==0)phi[u]=phi[a]*pr[i],i=le;
			else phi[u]=phi[a]*(pr[i]-1);
		}
	}
}
int n,k;
const int m=17;
ll dp[MAXN][18];
struct zkw{
	ll f[MAXN*3],lz[MAXN*3];int p;
	inline void init(int n){
		for(p=1;p0;i--)f[i]=INF;
	}
	inline void cg(int x,ll d){
		for(f[p+x]=d,x=(p+x)>>1;x;x>>=1)
			f[x]=min(f[x<<1],f[x<<1|1])+lz[x];
	}
	inline void add(int r,ll d){
		for(r=p+r+1;r>1;){
			if(r&1)f[r^1]+=d,lz[r^1]+=d;
			r>>=1,f[r]=min(f[r<<1],f[r<<1|1])+lz[r];
		}
	}
}T[17];
vectorZ[MAXN];
signed main()
{
	n=1e5,init(n);
	memset(dp,0x7f,sizeof(dp));
	for(int i=0;im||(1<n)print(n);
		else print(dp[n][k]);
	}
	return 0;
}