题解：P7810 [JRKSJ R2] Upper

· · 题解

题目描述

有 n 张扑克，第 i 张扑克上写有一个正整数 a_i。

现在要把扑克划分成若干个合法的连续子段，其中，一个连续子段 [l,r]“合法”当且仅当这个子段同时满足两个条件：

请问最多能划分多少段。如果没有合法的划分方案，输出 -1 即可。

Solution

不妨先来想一想暴力的 dp 怎么写。

不难想到令 f_i 为以 i 结尾的最多段数，则可写出方程：

dp_i= \max \limits _{j=1} ^{i-1} (dp_j+1)[(\gcd(a_j,a_i)>1) ~\land~ (a_i>a_j) ]

其中中括号里的代表转移条件，\land 代表且。

时间复杂的 O(n^2)，考虑优化。

如果只考虑 a_l<a_r 这个条件，我们不难想到值域的数据结构优化。

现在我们可以考虑 \gcd(a_l,a_r) > 1 的特殊性。

不妨先将 a_l,a_r 质因数分解，如果 \gcd(a_l,a_r) > 1 则它们必定包含相同的质因数。利用这条性质，我们可以将所有 a_i 所包含的质因数中给每一个质因数开一棵树状数组。

再结合 a_l<a_r 这个条件，我们就可以改成开值域数组数组。

但是有一个雷点就是不要离散化之后直接丢进去，因为当前 a_i 是质因数的倍数，所以可以将这个倍数离散化之后再塞进去，这样即可避免 MLE。

Tips

开树状数组时一定要用 vector，并且不要长度开多了。

dp 数组和树状数组一定要初始化为负无穷，不然就像我一样条半天。

Code

#include<bits/stdc++.h>
#define debug cout<<"fuck you"<<endl;
#define int long long
using namespace std;
const int N=3e5+5;

bool vis[N];
int pri[N],cnt;

void ol(int SZ){//预处理素数 
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    for(int i=2;i<=SZ;i++){
        if(vis[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt && pri[j]*i<=SZ;j++){
            vis[pri[j]*i]=0;
            if(i%pri[j]==0) break;
        }
    }
//  for(int i=1;i<=cnt;i++) cout<<pri[i]<<" ";
}

vector<int> d[N],tmp_d[N];//d[i]为第i个数的质因数集合 
int num_d[N];
void push_d(int x,int num){//分解质因数 
    for(int i=1;pri[i]*pri[i]<=x;i++){
        if(x%pri[i]==0){
            d[num].push_back(pri[i]);
            while(x%pri[i]==0) x/=pri[i];
        } 
    } 
    if(x!=1) d[num].push_back(x);
    return;
} 

int lowbit(int x){
    return x&-x;
}
struct FK_tree{//树状数组 
    vector<int> tr;
    int max_n;
    void init(int xx){
        max_n=xx+1;
        tr.resize(xx+10,-1e9);
    }
    int ask(int fk){
        int res=-1e9;
        for(;fk;fk-=lowbit(fk))
            res=max(res,tr[fk]);
        return res;
    }
    void change(int fk,int fq){
        for(;fk<=max_n;fk+=lowbit(fk))
            tr[fk]=max(tr[fk],fq);
    }
};

int get_rnk(int trr,int val){//离散化后获取倍数的排名 
    vector<int>::iterator iter = tmp_d[trr].begin() + num_d[trr]; //一定要用迭代器 
    return lower_bound(tmp_d[trr].begin(),iter,val) - tmp_d[trr].begin() + 1;//+1是为了避免RE 
}

vector<FK_tree> tree;
int a[N],n,tot,f[N],tot_tr;
map<int,int> mp,trmp;
signed main(){
    tree.resize(2e5);
    ol(2e5);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) push_d(a[i],i);
    memset(f,-0x7f,sizeof f);
    f[1]=-1; 
    for(int i=1;i<=n;i++)
        for(int j=0;j<d[i].size();j++)
            if(trmp[d[i][j]]==0) trmp[d[i][j]]=++tot_tr,tree[trmp[d[i][j]]].init(2*N/d[i][j]);
    //cout<<tot_tr;
    for(int i=1;i<=n;i++)
        for(int j=0;j<d[i].size();j++)
            tmp_d[trmp[d[i][j]]].push_back(a[i]);

    for(int i=1;i<=tot_tr;i++){
        sort(tmp_d[i].begin(),tmp_d[i].end());
        num_d[i]=unique(tmp_d[i].begin(),tmp_d[i].end()) - tmp_d[i].begin();
    }
    for(int j=0;j<d[1].size();j++)
        tree[trmp[d[1][j]]].change(get_rnk(trmp[d[1][j]],a[1]),0);
    for(int i=2;i<=n;i++){
        for(int j=0;j<d[i].size();j++)
            f[i]=max(f[i],tree[trmp[d[i][j]]].ask(get_rnk(trmp[d[i][j]],a[i])-1)+1);
        for(int j=0;j<d[i+1].size();j++)//下一个区间的开头，所以要 +1 
            tree[trmp[d[i+1][j]]].change(get_rnk(trmp[d[i+1][j]],a[i+1]),f[i]); 
    }
    if(f[n]<0) cout<<-1;
    else cout<<f[n];
}