题解：P13465 [GCJ 2008 #1C] Increasing Speed Limits

· · 题解

题解：P13465 [GCJ 2008 #1C] Increasing Speed Limits

题目传送门

主体思路

首先先读题，之后就可以开始爆想。之后我们会得到这道题的暴力思路： 设 dp_i 表示以第 i 个数结尾的严格递增子序列个数。转移方程即为：

dp[i]=1+\sum_{j<i,{a_j<a_i}}dp[j]

又因为这道题常数过大，所以我们需要进行树状数组优化：

\sum_{a_j<a_i}dp[j]

用树状数组维护权值前缀和。

之后我们可以开始 DP。

最后累加所有值，会得到最终答案。

再修改一下细节，你就会得到一篇 AC 代码。

逻辑总结

  1. 生成题目要求的数组。

  2. 离散化压缩数值范围。

  3. 树状数组维护前缀和。

  4. DP：每个数为前面比它小的和加一。

  5. 累加所有值得到答案。

    时间复杂度

    总复杂度为：O(n\log n) 可以轻松通过。

    代码实现

    代码里的思路非常详细，有需要者可以阅读。

    #include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;       
const int mod=1e9+7;  
int t,n,m,x,y,z,a[N];     
int bs[N];         
int tr[N];       
vector<int> g;     
inline int lowbit(int x){//lowbit函数，不用多解释 
return x&(-x);
}
inline void update(int x,int val){//单点更新 
for(int i=x;i<N;i+=lowbit(i)){
    tr[i]=(tr[i]+val)%mod;
}
}
inline int query(int x){//区间查询 
int res=0;
for(int i=x;i>=1;i-=lowbit(i)){
    res=(res+tr[i])%mod;
}
return res;
}
inline int solve(int x){//找出对应下标 
return lower_bound(g.begin(),g.end(),x)-g.begin()+1;
}
signed main(){
ios::sync_with_stdio(0);  
cin.tie(0); 
cout.tie(0);
cin>>t;                  
int tmp=0;     
while(t--){
    tmp++;
    cin>>n>>m>>x>>y>>z;   
    for(int i=0;i<m;i++){ 
        cin>>bs[i];
    }
    g.clear();//数据清空，不然会被创飞 
    for(int i=1;i<=n;i++){
        int pos=(i-1)%m;//取模循环使用种子数组
        a[i]=bs[pos];//赋值到当前序列
        bs[pos]=(x*bs[pos]+y*i)%z;//按公式更新
        g.push_back(a[i]);//加入离散化
    }
    //离散化 
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());

    memset(tr,0,sizeof(tr));//数据清空，不然会被创飞 
    int ans=0;         
    for(int i=1;i<=n;i++){//开始dp 
        int rk=solve(a[i]);//获得当前值离散化后的排名
        int sum=query(rk-1);//求比当前数小的所有dp和
        int now=(sum+1)%mod;//+1表示只选自己的子序列
        ans=(ans+now)%mod;//累加到总答案
        update(rk,now);//当前 dp 值加入树状数组
    }
    cout<<"Case #"<<tmp<<": "<<ans<<'\n'; 
}
return 0;
}
//码风较为紧凑，不喜勿喷。
//蒟蒻写了两年半才写完，QWQ。