P11106 题解

DaiRuiChen007 · 2024-08-19 10:28:43 · 题解

Problem Link

题目大意

给定 n 阶排列 p，分成两个子序列 q,r，最大化 q 中 Local-Max 个数加上 r 中 Local-Min 个数。

数据范围：n\le 2\times 10^5。

思路分析

考虑 q,r 第一次值域相交的时刻 a_i，那么在 (i,n] 范围内可以直接取 LIS 和 LDS，其他元素可以直接放到对面的序列里，不影响对面的 Local-Max 或 Local-Min。

在 a_i 之前，q 一定取 <a_i 所有数，r 一定取 >a_i 所有数，可以用 std::set 对每个 x 维护 a_i=x 时当前 q,r 对应的权值和。

然后枚举 a_i 属于 q/r，如果属于 q，那么就取 a(i,n] 中值域 <\min r[1,i) 和 >\min r[1,i) 的 LIS 和 LDS，倒序扫描线，树状数组维护。

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

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n,a[MAXN],pre[MAXN],suf[MAXN],f[MAXN],w[MAXN];
struct FenwickTree1 {
    int tr[MAXN],s;
    void init() { fill(tr,tr+n+1,0); }
    void add(int x,int v) { for(;x<=n;x+=x&-x) tr[x]=max(tr[x],v); }
    int qry(int x) { for(s=0,x=min(x,n);x;x&=x-1) s=max(s,tr[x]); return s; }
}   T1;
struct FenwickTree2 {
    int tr[MAXN],s;
    void init() { fill(tr,tr+n+1,0); }
    void add(int x,int v) { for(;x;x&=x-1) tr[x]=max(tr[x],v); }
    int qry(int x) { for(s=0,x=max(x,1);x<=n;x+=x&-x) s=max(s,tr[x]); return s; }
}   T2;
void solve() {
    scanf("%d",&n); int ans=0;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    set <int> S{0,n+1}; f[0]=f[n+1]=0;
    for(int i=1;i<=n;++i) {
        auto it=--S.upper_bound(a[i]);
        w[i]=f[a[i]]=++f[*it],pre[i]=*it,suf[i]=*++it,S.insert(a[i]);
    }
    T1.init(),T2.init();
    for(int i=n;i>=1;--i) {
        ans=max(ans,w[i]+T1.qry(pre[i])+T2.qry(pre[i]));
        ans=max(ans,w[i]+T1.qry(suf[i])+T2.qry(suf[i]));
        T1.add(a[i],T1.qry(a[i])+1),T2.add(a[i],T2.qry(a[i])+1);
    }
    printf("%d\n",ans);
}
signed main() {
    int Q; scanf("%d",&Q);
    while(Q--) solve();
    return 0;
}