题解：CF2171H Shiori Miyagi and Maximum Array Score

· · 题解

思路

先考虑朴素的 dp 方程。dp_{i,j} 表示：到第 i 位，a_i=j 时的答案。

初始 dp_{1,1}=0。转移方程为 dp_{i,j}=\max_{k=1}^{j-1}dp_{i-1,k}+v(i,j)。

如果只考虑最优的状态，状态是 n\ln(n) 的。

:::info[证明] 因为如果 v(i,k)=0 的话就只会继承前面的状态。如果 v(i,k)\not =0 的话就是一个新的状态。根据调和级数状态数就是 n\ln(n) 的。 :::

这东西一眼可以想到用平衡树做。每次对于所有 v(i,k)=0 的情况就是把前面所有的状态平移一下,打个懒标记就行。新建状态的话就是平衡树上查前缀最大值，在一起插入进平衡树。

时间复杂度：O(n\ln n\log n)。

要注意的是每个状态不能每次新建一个点，这样平衡树的节点会变成 n\ln n 个，复杂度就不对了。

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
void init();void Solve();
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T=1;init();
    cin>>T;
    while(T--) Solve();
    return 0;
}
void init(){
}
int n,m;
vector<pair<int,int> > q;
struct TREE{
    int rt,cnt;
    struct node{
        int num,val,rad,mx,ls,rs,tag;
    }t[200005<<5];
    void push_down(int u){
        if(t[u].ls) t[t[u].ls].num+=t[u].tag,t[t[u].ls].tag+=t[u].tag;
        if(t[u].rs) t[t[u].rs].num+=t[u].tag,t[t[u].rs].tag+=t[u].tag;
        t[u].tag=0;
    }
    void push_up(int u){
        t[u].mx=t[u].val;
        if(t[u].ls) t[u].mx=max(t[u].mx,t[t[u].ls].mx);
        if(t[u].rs) t[u].mx=max(t[u].mx,t[t[u].rs].mx);
    }
    void split(int u,int o,int &x,int &y){
        if(!u){
            x=y=0;
            return;
        }
        push_down(u);
        if(t[u].num<=o){
            split(t[u].rs,o,t[u].rs,y);
            x=u;
        }
        else{
            split(t[u].ls,o,x,t[u].ls);
            y=u;
        }
        push_up(u);
    }
    int merge(int x,int y){
        if(!x||!y) return x|y;
        push_down(x);push_down(y);
        if(t[x].rad<t[y].rad){
            t[x].rs=merge(t[x].rs,y);
            push_up(x);return x;
        }
        else{
            t[y].ls=merge(x,t[y].ls);
            push_up(y);return y;
        }
    }
    void add(int x,int y){
        int l=0,mid=0,r=0;
        split(rt,x,l,r);
        split(l,x-1,l,mid);
        if(!mid){
            mid=++cnt;
            t[mid].num=x;t[mid].val=t[mid].mx=y;t[mid].rad=rand();t[mid].ls=t[mid].rs=t[mid].tag=0;
        }
        else t[mid].val=t[mid].mx=max(t[mid].val,y);
        rt=merge(l,merge(mid,r));
    }
    int query(int x){
        int l=0,r=0,res=0;
        split(rt,x,l,r);
        res=t[l].mx;
        rt=merge(l,r);
        return res;
    }
}T;
void Solve(){
    srand(time(0));
    cin>>n>>m;
    T.cnt=T.rt=0;
    T.add(1,0);
    for(int i=2;i<=n;i++){
        T.t[T.rt].tag++;T.t[T.rt].num++;q.clear();
        for(int j=i,c,x;j<=m;j+=i){
            x=j,c=0;
            while(x%i==0) x/=i,c++;
            q.push_back({j,T.query(j)+c});
        }
        for(auto [x,y]:q) T.add(x,y);
    }
    cout<<T.query(m)<<endl;
}