也会有发光的一天吖

```c
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define debug(x) cout<<"target is "<<x<<endl
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define all(a) a.begin(),a.end()
#define oper(a) (operator<(const a& ee)const)
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 200010, M = 500010, MM = 110;
int INF = 0x3f3f3f3f, mod = 998244353;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
int z[N], dpl[N], dpr[N];
vector<int> vec;
int find(int x) { //离散化排序后二分查找元素位置
    return lower_bound(all(vec), x) - vec.begin() + 1;
}

struct tree
{
    int l, r, mx;
}tr[N << 2];
inline void pushup(int u) {
    tr[u].mx = max(tr[ul].mx, tr[ur].mx);//维护max
}
void build(int u, int l, int r) {
    if (l == r)tr[u] = { l,r,0 };
    else {
        tr[u] = { l,r,0 };
        int mid = l + r >> 1;
        build(ul, l, mid), build(ur, mid + 1, r);
    }
}
void modify(int u, int d, int f) {
    if (tr[u].l == d && tr[u].r == d) {
        tr[u].mx = f;
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (mid >= d)modify(ul, d, f);
        if (mid < d)modify(ur, d, f);
        pushup(u);
    }
}
int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        return tr[u].mx;
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        int t = 0;
        if (mid >= l)t = query(ul, l, r);
        if (mid < r)t = max(t, query(ur, l, r));
        return t;
    }
}

void solve() {
    cin >> n >> k;
    forr(i, 1, n)cin >> z[i], vec.push_back(z[i]);
    sort(all(vec));
    vec.erase(unique(all(vec)), vec.end());

m = vec.size();
    build(1, 1, m);

int ans = k;

//先用这个思想维护出从左到右 i 位置的最长不下降子序列
    forr(i, 1, n) {
        int t = find(z[i]);
        int res = query(1, 1, t) + 1;
        //从小于等于z[i]的区间中找 max(dpl值)

dpl[i] = res;
        ans = max(ans, dpl[i]);

modify(1, t, res);
        //同时更新此位置，维护此位置 max(dpl值)
    }

build(1, 1, m);

//同样维护从右到左 i 位置的最长不上升子序列
    for (int i = n; i; i--) {
        int t = find(z[i]);
        int res = query(1, t, m) + 1;
        dpr[i] = res;
        ans = max(ans, dpr[i]);
        modify(1, t, res);

//但这里维护的同时要随时与 k 个前的 dpl[be] 取 max
        int be = i - k - 1;
        if (be >= 1) {
            int tt = find(z[be]);
            ans = max(ans, dpl[be] + k + query(1, tt, m));
            //维护到此位置的权值线段树中，在比 z[be] 大的区间中找 max 值

//这样才能保证没有遗漏，因为中间可能不止空出 k 个数
        }
    }

//最后还有记录不连接两区间，直接加 k 的情况
    for (int i = 1; i + k <= n; i++)
        ans = max(ans, dpl[i] + k);
    for (int i = n; i - k >= 1; i--)
        ans = max(ans, dpr[i] + k);

cout << ans;
}

int main() {
    cinios;
    int T = 1;
    forr(t, 1, T) {
        solve();
    }
    return 0;
}
/*
8 2
5 6 100 99 98 97 7 8

//答案是 6
*/

```

0.0分

3 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

也会有发光的一天吖

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

蓝桥杯2022年第十三届省赛真题-最长不下降子序列

评论区

精彩推荐

大小写转换（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

淘淘的名单（C语言代码）

printf基础练习2 （C语言代码）

求圆的面积（C语言代码）

1071题解

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）

也会有发光的一天吖

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （Java代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

蓝桥杯2022年第十三届省赛真题-最长不下降子序列

评论区

精彩推荐

大小写转换 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

淘淘的名单 （C语言代码）

printf基础练习2 （C语言代码）

求圆的面积 （C语言代码）

1071题解

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

青年歌手大奖赛_评委会打分 （C语言代码）

　　评论区

大小写转换（C语言代码）

淘淘的名单（C语言代码）

求圆的面积（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）