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

· · 题解

前言

提供一个不同的做法。

题解

这个东西显然考虑 dp。设 f_{i,j} 表示考虑前 i 个数，钦定选 i，并且选择的数的最大值为 j 的答案。

首先因为选了 i 所以有 f_{i,j}=0(j\in[0,a_i))，然后考虑转移。分讨当前选择的数是否是最大值，如果不是那么有 f_{i,j}=f_{k,j}(i-d\le k<i,j>a_i)，否则就有 f_{i,a_i}=\max(f_{j,k}+1,f_{j,a_i})(i-d\le j<i,k<a_i)。可以发现前面的转移是类似继承的，后面的转移是对于单点的，于是可以看成一个状态数 \mathcal O(n^2) 但是转移状态 \mathcal O(1) 的 dp，考虑转移需要找矩形最大值，于是考虑扫描线扫 i 然后用线段树维护第二维。

但是这样是有一点问题的，因为我们的转移是矩形最值，而扫描线只能维护一个线段的信息，所以我们考虑将矩形信息压进一个线段中。于是我们用线段树维护 [i-d,i] 的信息，现在考虑从 i 到 i+1 的时候，我们要做的就是删去线段树中 f_{i-d} 的信息。考虑每个 f_i 有贡献的区间是一段后缀，所以删掉一个 f_i 之后线段树中有贡献的值域就可能会变成一个更短的后缀。我们把这个过程看成在值域上的线段覆盖，只有当一个位置被覆盖的次数大于零才有贡献，否则就把这个位置的贡献清空。所以我们考虑再开一棵线段树维护线段覆盖，以及快速找第一个有贡献的位置，这个可以线段树二分处理。时间复杂度为 \mathcal O(n\log n)。

代码

/*
 * @Author: Nekopedia 
 * @Date: 2025-11-22 10:48:14 
 * @Last Modified by: Nekopedia
 * @Last Modified time: 2025-11-22 14:26:31
 */
#include <bits/stdc++.h>
#define ll long long
#define gc() (p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, S, stdin), p1 == p2) ? EOF : *p1++)
#define pc putchar
using namespace std;
const int N = 3e5 + 5, S = 1 << 22;
char buf[S], *p1, *p2;
inline ll rd(){
    ll x = 0, f = 1; char c = gc();
    while(! isdigit(c)){if(c == '-')f = - f; c = gc();}
    while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
    return x * f;
}
inline void wt(ll x){
    if(x < 0)pc('-'), x = - x; static short st[20], top(0);
    do st[++top] = x % 10, x /= 10; while(x);
    while(top)pc(st[top--] ^ 48);
}
void fileio(const string &s){
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int n, m, d, a[N], b[N];
#define ls x << 1
#define rs ls | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
int ma[N << 2], tg[N << 2];
inline void pu1(int x){ma[x] = max(ma[ls], ma[rs]);}
inline void add(int x, int y){ma[x] = tg[x] = y;}
inline void pd(int x){if(~ tg[x])add(ls, tg[x]), add(rs, tg[x]); tg[x] = - 1;}
inline void mdf1(int x, int l, int r, int ql, int qr, int y){
    if(ql <= l and r <= qr)return add(x, y); int mid = l + r >> 1; pd(x);
    if(ql <= mid)mdf1(lson, ql, qr, y); if(mid < qr)mdf1(rson, ql, qr, y); pu1(x);
}
inline int qry(int x, int l, int r, int ql, int qr){
    if(ql <= l and r <= qr)return ma[x]; int mid = l + r >> 1; pd(x);
    return max(ql <= mid ? qry(lson, ql, qr) : 0, mid < qr ? qry(rson, ql, qr) : 0);
}
int s[N << 2];
inline void pu2(int x){s[x] = s[ls] + s[rs];}
inline void mdf2(int x, int l, int r, int p, int y){
    if(l == r)return s[x] += y, void(); int mid = l + r >> 1;
    p <= mid ? mdf2(lson, p, y) : mdf2(rson, p, y); pu2(x);
}
inline int fd(int x, int l, int r){
    if(l == r)return l; int mid = l + r >> 1;
    if(! s[ls])return fd(rson); return fd(lson);
}

const string FileName = "qyuan";
signed main(){
    fileio(FileName);
    n = rd(), d = rd();
    for(int i = 1; i <= n; ++i)a[i] = b[i] = rd();
    sort(a + 1, a + 1 + n); m = unique(a + 1, a + 1 + n) - a - 1;
    for(int i = 1; i <= n; ++i)b[i] = lower_bound(a + 1, a + 1 + m, b[i]) - a;
    for(int i = 1; i <= m << 2; ++i)tg[i] = - 1;
    for(int i = 1; i <= n; ++i){
        if(i - d > 1)mdf2(1, 1, m, b[i - d - 1], - 1);
        int r = fd(1, 1, m); if(i - d > 1 and b[i - d - 1] < r)
            mdf1(1, 1, m, b[i - d - 1], r - 1, 0);
        mdf2(1, 1, m, b[i], 1);
        if(b[i] > 1){
            int x = max(qry(1, 1, m, 1, b[i] - 1) + 1, qry(1, 1, m, b[i], b[i]));
            mdf1(1, 1, m, b[i], b[i], x);
        }
        else mdf1(1, 1, m, 1, 1, 1);
    }
    return wt(qry(1, 1, m, b[n], m)), 0;
}
// 于是纵横万相穷通 也守心底灵通
// 合眼识得星沉地动 也岿然不动
// 敢令岁月乌有 逍遥长驻 敢归云间宿
// 遥祝远行人 有道不孤