【CF1647F】Madoka and Laziness

· · 题解

你小圆怎么 Div2 F 撞原 Div3 G 啊（恼）。我怎么半年前就做过场上还是不会啊（雾）

如果大家这个题有点困难可以先去学习核心部分的解法 CF1144G ，然后很快就懂了。

题意有点绕。就是说定义一个好的序列为先严格上升再严格下降。称最大值为拐点，记作 \alpha。

然后给你一个 n 个数互不相同的数列 a，让你拆成两个非空的好序列，记两个序列的拐点为 \alpha_1\lt \alpha_2，然后就是问你 (\alpha_1,\alpha_2) 有多少种可能。

这个题诈骗性质很强，因为你注意到 \alpha_2 必定是 a 数组最大值。所以答案不超过 n-1：我们只用考虑暴力枚举 \alpha_1 并判断是否有拆分方式即可。

然后不失一般性我们可以设 \alpha_1 的位置在最大值的右边（左边的话可以翻转数列再做一遍）。

这样整个数列应该被分成三部分：最左边的部分被拆成两个上升子序列，中间部分被拆成一个下降和一个上升的子序列，最右边的部分被拆成两个下降子序列。

这三个问题本质上是相近的，如果做过 CF1144G 这样的问题应该就立马会做了（除了我）。

我们就来分开来考虑三个问题好了：给定一个序列，能否拆成两个上升子序列（第一部分）；或者一个上升一个下降的子序列（第二部分）；或者两个下降子序列（第三部分）。

注意到第一部分和第三部分本质是相同的。我们只考虑第一部分和第二部分怎么做。

这部分很有趣，解决这类“二择”问题，关键是我们发现每个元素必定属于两个上升序列的一个，而上升/下降序列的话，我们只关注结尾的值，所以有这样一个想法：设 f(1,i) 是前 i 个元素，第 i 个元素被划分进了第一个序列，此时第二个序列结尾的最优秀值（如果第二个序列是下降的，就是结尾的最大值；如果第二个序列是上升的，就是结尾的最小值。）；同理 f(2,i) 是前 i 个元素，第 i 个元素被划分进了第二个序列，此时第二个序列结尾的最优秀值。

然后转移的思想是这样的：考虑 i-1 和 i，因为要么 i-1 和 i 划分进同一个序列，要么不在同一个序列。对于第一种情况，f(i) 直接继承 f(i-1) 就好了；对于第二种情况，f(i) 就直接从 a_{i-1} 继承。

另外我们注意到，对于第一部分和第三部分 f(1,i)=f(2,i)，所以这里我们就直接记作 f(i) 了。

然后考虑把左中右三段拼接起来。左和中的拼接是容易的，我们只是把左边 f(maxpos) 的信息作为中间一段的 f 数组的初始化。而中和右的拼接实质上就是枚举 \alpha_2 的位置 pos，然后判断其合法性，就是中间的 f(2,pos) 要大于右边的 f(pos)。

这样，时间复杂度是 O(n) 的！

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=5e5+10,INF=2e9;
int n,ans,a[MAXN];
int f1[MAXN],f2[MAXN],g[2][MAXN];
void solve(){
    int maxpos=1;rep(i,2,n)if(a[i]>a[maxpos])maxpos=i;
    f1[0]=-INF;
    rep(i,1,maxpos){
        f1[i]=INF;
        if(a[i-1]<a[i])f1[i]=min(f1[i],f1[i-1]);
        if(f1[i-1]<a[i])f1[i]=min(f1[i],a[i-1]);
    }
    f2[n+1]=-INF;
    per(i,n,maxpos){
        f2[i]=INF;
        if(a[i+1]<a[i])f2[i]=min(f2[i],f2[i+1]);
        if(f2[i+1]<a[i])f2[i]=min(f2[i],a[i+1]);
    }
    g[0][maxpos]=f1[maxpos];
    g[1][maxpos]=-INF;
    rep(i,maxpos+1,n){
        g[0][i]=INF;g[1][i]=-INF;
        if(a[i-1]>a[i])g[0][i]=min(g[0][i],g[0][i-1]);
        if(g[1][i-1]>a[i])g[0][i]=min(g[0][i],a[i-1]);
        if(a[i-1]<a[i])g[1][i]=max(g[1][i],g[1][i-1]);
        if(g[0][i-1]<a[i])g[1][i]=max(g[1][i],a[i-1]);
    }
    rep(i,maxpos+1,n){
        if(g[1][i]>f2[i])ans++;
    }
}
int main(){
    cin>>n;
    rep(i,1,n)cin>>a[i];
    solve();
    reverse(a+1,a+1+n);
    solve();
    cout<<ans;
    return 0;
}