题解：P7804 [JOI Open 2021] 决算报告 / Financial Report

· · 题解

题意

由于本题题面描述过于抽象，所以先来翻译一下题意。

给出一个长为 n 的序列 A，请你选出 A 的一个子序列 p ，要求子序列的相邻两项在原序列中的位置的差 \le D。定义一个子序列的收益是 \sum\limits_{A_i \in p} [A_i > A_j] (A_j \in p, j<i) ，求最大收益。

做法

在下文中，称“关键元素”为在子序列中满足 [A_i > A_j] (A_j \in p, j<i) 的 A_i。

首先考虑设 dp_i 表示以第 i 个元素为末个关键元素的子序列的最大收益值，那么转移即为 dp_i=\max\limits_{j<i,A_j<A_i} dp_j。

现在考虑“相邻两项在原序列中的位置的差 \le D”这一限制该如何转化为判定合法的 j 的条件。我们发现，“i 和 j 之间不存在一个所有元素均 \ge A_i 的连续段”是 j 合法的充要条件。

证明省略，比较简单，读者可以尝试自己证一下。

通过进一步思考，发现合法的 j 是连续的（不是真的连续，因为还有对 A_j 的大小限制，不过如果把 A_j<A_i 的所有 A_j 抽出来，合法的 j 就是连续的了），这提示我们可以使用数据结构来优化 dp。

为了“去除”掉大小的限制，我们先按 A_i 从小到大排序（如果 A_i=A_j，则位置靠后的更小），这样后面的转移就可以不考虑大小了，因为所有已经被更新过的 dp_j 均有 A_j<A_i。

可以弄一个 set 用来维护已经更新过的 dp_j 的下标。设 k 是 set 中 i 的前一项，也就是 <i 的最大的已经更新过的位置，如果 i-k \le D 那么 k 就是一个合法的转移点。转移点具有“传递性”，因为可以一个一个往前“跳”。所以我们维护一个并查集，i 所在的集合的祖先就是 i 可以往前跳到的下标最小的转移点。

于是我们就获得了做法：排序后，从小到大更新 dp 值，每次更新第 i 个元素的时候，判一下 i 前后两个位置与它的差是否 \le D，如果是则合并两个集合。所以 dp_i=\max\limits_{\text{find(i)} \le j < i} dp_j，这个直接用线段树维护区间最大值即可，更新完 i 后，更改其在线段树上的值即可。

代码

个人认为还是比较具有可读性的：

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,D,ans=0,fa[N];
struct F{int x,id;}a[N];
bool cmp(F a,F b) {return a.x==b.x?a.id>b.id:a.x<b.x;}
struct Node{int l,r,mx;}tree[N<<2];
void pushup(int p) {tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);}
void build(int p,int l,int r) { 
    tree[p].l=l,tree[p].r=r,tree[p].mx=0;
    if (l==r) return ;
    int mid=(l+r)>>1;
    build(p*2,l,mid); build(p*2+1,mid+1,r);
}
void modify(int p,int x,int k) {
    if (tree[p].l==tree[p].r) {tree[p].mx=max(tree[p].mx,k); return ;}
    int mid=(tree[p].l+tree[p].r)>>1;
    if (x<=mid) modify(p*2,x,k);
    else modify(p*2+1,x,k);
    pushup(p);
}
int query(int p,int l,int r) {
    if (l<=tree[p].l&&tree[p].r<=r) return tree[p].mx;
    int mid=(tree[p].l+tree[p].r)>>1,res=0;
    if (l<=mid) res=max(res,query(p*2,l,r));
    if (r>mid) res=max(res,query(p*2+1,l,r));
    return res;
}
inline int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void Merge(int u,int v) {
    int fu=find(u),fv=find(v);
    fa[max(fu,fv)]=min(fu,fv);
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>D; build(1,1,n);
    for (int i=1;i<=n;i++) cin>>a[i].x,a[i].id=i,fa[i]=i;
    sort(a+1,a+n+1,cmp); set<int> now;
    for (int i=1;i<=n;i++) {
        int id=a[i].id; now.insert(id);
        auto p=now.find(id);
        int lst=(p!=now.begin()?(*prev(p)):-1),nxt=(next(p)!=now.end()?(*next(p)):-1);
        if (lst!=-1&&id-lst<=D) Merge(lst,id);
        if (nxt!=-1&&nxt-id<=D) Merge(id,nxt);
        int dp=query(1,find(id),id)+1; ans=max(ans,dp);
        modify(1,id,dp);
    }
    cout<<ans<<"\n";
    return 0;
}