【最长不下降子序列——树状数组、线段树、LIS】
题目

代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N], b[N], tr[N];//a保存权值,b保存索引,tr保存f,g前缀属性最大值
int f[N], g[N];
int n, m;
bool cmp(int x, int y)
{if(a[x] != a[y]) return a[x] < a[y]; //不下降,因此值递增return x < y; //不下降,允许重复,保留等于号(不保留是x > y,代表逆序,自然不成序列)
}
void modify(int x, int val)
{for(; x <= n; x += x & -x){tr[x] = max(tr[x], val);}
}
int query(int x)
{int retv = 0;for(; x; x -= x & -x){retv = max(retv, tr[x]);}return retv;
}
int main()
{cin >> n >> m;for(int i = 1; i <= n; i++)cin >> a[i], b[i] = i;sort(b+1, b+n+1, cmp);int ans = 0, tmp;for(int i = 1; i <= n; i++){int p = b[i];f[p] = query(p-1) + 1;tmp = 0;if(p + m <= n) tmp = m;ans = max(ans, f[p] + tmp);modify(p, f[p]);}memset(tr, 0, sizeof tr);for(int i = n; i >= 1; i--){int p = n + 1 - b[i];g[b[i]] = query(p-1) + 1;tmp = 0;if(b[i] - m >= 1) tmp = m;ans = max(ans, tmp + g[b[i]]);modify(p, g[b[i]]);}memset(tr, 0, sizeof tr);for(int i = 1; i <= n; i++){int p = b[i];if(p > m+1) ans = max(ans, query(p - m - 2) + m + g[p]);modify(p, f[p]);}cout << ans;
}
相关文章:
【最长不下降子序列——树状数组、线段树、LIS】
题目 代码 #include <bits/stdc.h> using namespace std; const int N 1e510; int a[N], b[N], tr[N];//a保存权值,b保存索引,tr保存f,g前缀属性最大值 int f[N], g[N]; int n, m; bool cmp(int x, int y) {if(a[x] ! a[y]) return a[x] < a[…...
【实战篇章】深入探讨:服务器如何响应前端请求及后端如何查看前端提交的数据
文章目录 深入探讨:服务器如何响应前端请求及后端如何查看前端提交的数据一、服务器如何响应前端请求HTTP 请求生命周期全解析1.前端发起 HTTP 请求(关键细节强化版)2. 服务器接收请求(深度优化版) 二、后端如何查看前…...
Games104——引擎工具链基础
总览 工具链 用户到引擎架构图 工具链是衔接不同岗位、软件之间的桥梁,比如美术与技术,策划与美术,美术软件与引擎本身等,有Animation、UI、Mesh、Shader、Logical 、Level Editor等等。一般商业级引擎里的工具链代码量是超过…...
分层多维度应急管理系统的设计
一、系统总体架构设计 1. 六层体系架构 #mermaid-svg-QOXtM1MnbrwUopPb {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-QOXtM1MnbrwUopPb .error-icon{fill:#552222;}#mermaid-svg-QOXtM1MnbrwUopPb .error-text{f…...
【漏斗图】——1
🌟 解锁数据可视化的魔法钥匙 —— pyecharts实战指南 🌟 在这个数据为王的时代,每一次点击、每一次交易、每一份报告背后都隐藏着无尽的故事与洞察。但你是否曾苦恼于如何将这些冰冷的数据转化为直观、吸引人的视觉盛宴? 🔥 欢迎来到《pyecharts图形绘制大师班》 �…...
(二)QT——按钮小程序
目录 前言 按钮小程序 1、步骤 2、代码示例 3、多个按钮 ①信号与槽的一对一 ②多对一(多个信号连接到同一个槽) ③一对多(一个信号连接到多个槽) 结论 前言 按钮小程序 Qt 按钮程序通常包含 三个核心文件: m…...
【Linux】从硬件到软件了解进程
个人主页~ 从硬件到软件了解进程 一、冯诺依曼体系结构二、操作系统三、操作系统进程管理1、概念2、PCB和task_struct3、查看进程4、通过系统调用fork创建进程(1)简述(2)系统调用生成子进程的过程〇提出问题①fork函数②父子进程关…...
HTB:Alert[WriteUP]
目录 连接至HTB服务器并启动靶机 信息收集 使用rustscan对靶机TCP端口进行开放扫描 使用nmap对靶机TCP开放端口进行脚本、服务扫描 使用nmap对靶机TCP开放端口进行漏洞、系统扫描 使用nmap对靶机常用UDP端口进行开放扫描 使用ffuf对alert.htb域名进行子域名FUZZ 使用go…...
ARM嵌入式学习--第十天(UART)
--UART介绍 UART(Universal Asynchonous Receiver and Transmitter)通用异步接收器,是一种通用串行数据总线,用于异步通信。该总线双向通信,可以实现全双工传输和接收。在嵌入式设计中,UART用来与PC进行通信,包括与监控…...
玉米苗和杂草识别分割数据集labelme格式1997张3类别
数据集格式:labelme格式(不包含mask文件,仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数):1997 标注数量(json文件个数):1997 标注类别数:3 标注类别名称:["corn","weed","Bean…...
哈夫曼树
哈夫曼树(Huffman Tree)是一种最优的二叉树,常用于数据压缩,如在 Huffman 编码中使用。它是根据字符出现的频率来构造的,频率越高的字符越靠近树的根,频率低的字符则在较深的节点上。其核心思想是通过构建一…...
wax到底是什么意思
在很久很久以前,人类还没有诞生文字之前,人类就产生了语言;在诞生文字之前,人类就已经使用了语言很久很久。 没有文字之前,人们的语言其实是相对比较简单的,因为人类的生产和生活水平非常低下,…...
笔记:使用ST-LINK烧录STM32程序怎么样最方便?
一般板子在插件上, 8脚 3.3V;9脚 CLK;10脚 DIO;4脚GND ST_Link 19脚 3.3V;9脚 CLK;7脚 DIO;20脚 GND 烧录软件:ST-LINK Utility,Keil_5; ST_Link 接口针脚定义: 按定义连接ST_Link与电路板; 打开STM32 ST-LINK Uti…...
数据分析系列--[11] RapidMiner,K-Means聚类分析(含数据集)
一、数据集 二、导入数据 三、K-Means聚类 数据说明:提供一组数据,含体重、胆固醇、性别。 分析目标:找到这组数据中需要治疗的群体供后续使用。 一、数据集 点击下载数据集 二、导入数据 三、K-Means聚类 Ending, congratulations, youre done....
Python在数据科学领域的深度应用:从数据处理到机器学习模型构建
Python在数据科学领域的深度应用:从数据处理到机器学习模型构建 在当今大数据与人工智能蓬勃发展的时代,Python凭借其简洁的语法、强大的库支持和活跃的社区,已成为数据科学家和工程师的首选编程语言。本文将深入探讨Python在数据科学领域的应用,从数据预处理、探索性分析…...
海外问卷调查渠道查,具体运营的秘密
相信只要持之以恒并逐渐掌握技巧,每一位调查人在踏上征徐之时都会非常顺利的。并在日后的职业生涯中拥有捉刀厮杀的基本技能!本文会告诉你如何做好一个优秀的海外问卷调查人。 在市场经济高速发展的今天,众多的企业为了自身的生存和发展而在…...
穷举vs暴搜vs深搜vs回溯vs剪枝系列一>单词搜索
题解如下 题目:解析决策树:代码设计: 代码: 题目: 解析 决策树: 代码设计: 代码: class Solution {private boolean[][] visit;//标记使用过的数据int m,n;//行,列char…...
万字长文深入浅出负载均衡器
前言 本篇博客主要分享Load Balancing(负载均衡),将从以下方面循序渐进地全面展开阐述: 介绍什么是负载均衡介绍常见的负载均衡算法 负载均衡简介 初识负载均衡 负载均衡是系统设计中的一个关键组成部分,它有助于…...
基于SpringBoot的青年公寓服务平台的设计与实现(源码+SQL脚本+LW+部署讲解等)
专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌。 技术范围:SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:…...
经典游戏红色警戒2之英语
1. New construction options 部署新的建筑物(一般是部署基地车时说的)。 2. Loading 等待。(正在进行) 3. Construction complete 建筑完成。 4. On hold 等待。(暂停进行) 5. Canceled 取消。 6. Ca…...
从“工具辅助”到“智慧赋能”:青软青之深度集成LIMS、ELN、AUTO等核心系统,打造全场景智慧实验室新范式
在科研创新迭代加速、检验检测产业升级纵深推进的今天,实验室作为创新源头,其运行效率与管理水平直接决定研发效能与质量。传统依赖人工记录、纸质流转和信息孤岛的模式,已难以适应复杂实验需求与严苛合规监管。智慧实验室,正成为…...
League-Toolkit:颠覆式英雄联盟客户端增强工具的全攻略
League-Toolkit:颠覆式英雄联盟客户端增强工具的全攻略 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power 🚀. 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League-Toolkit是一款基于官…...
MotorController:嵌入式伺服电机驱动的确定性执行封装
1. 项目概述MotorController是一个面向伺服系统电机控制的轻量级工具类,其设计目标并非替代完整的运动控制固件栈,而是为嵌入式工程师提供一套可直接集成、低侵入、高可控性的底层电机驱动封装。该类不依赖特定硬件抽象层(HAL)或实…...
Linux远程连接工具评测与选型指南
1. Linux远程连接工具概述作为一名嵌入式Linux开发者,我每天都需要通过远程连接工具访问各种开发板和服务器。在多年的实践中,我尝试过市面上几乎所有主流的远程终端工具,深知每款工具的特点和适用场景。选择一款合适的远程连接工具ÿ…...
嵌入式软件框架设计:从基础到实战
1. 嵌入式软件框架设计基础作为一名在嵌入式领域摸爬滚打多年的工程师,我深刻体会到框架设计对项目成败的决定性影响。嵌入式系统与通用计算机系统最大的区别在于其资源受限性和实时性要求,这就决定了我们不能简单套用桌面开发的思维模式。程序框架本质上…...
FLAC3D 6.0 和 7.0 版本输出塑形区体积及破坏区域体积那些事儿
FLAC3D输出塑形区体积,适用于6.0和7.0版本,输出剪切破坏区域,张拉破坏区域体积,如图2中所示在岩土工程数值模拟领域,FLAC3D 是一款相当强大的工具。今天咱就聊聊如何在 FLAC3D 6.0 和 7.0 版本中输出塑形区体积&#x…...
COMSOL相场法/水平集方法多孔介质两相驱替模型案例 附随机孔隙度几何程序 助力学习两相流驱替模拟
COMSOL相场法(/水平集方法)多孔介质驱替模型案例,可以提供随机孔隙度几何程序。 提供基于COMSOL中相场方法模拟多孔介质两相驱替(水气、油水等等)的算例(也可以定做水平集驱替的算例)࿰…...
如何彻底解决消息撤回难题?RevokeMsgPatcher带来的革新方案
如何彻底解决消息撤回难题?RevokeMsgPatcher带来的革新方案 【免费下载链接】RevokeMsgPatcher :trollface: A hex editor for WeChat/QQ/TIM - PC版微信/QQ/TIM防撤回补丁(我已经看到了,撤回也没用了) 项目地址: https://gitco…...
如何快速清理Windows 11臃肿:Win11Debloat完整优化指南
如何快速清理Windows 11臃肿:Win11Debloat完整优化指南 【免费下载链接】Win11Debloat A simple, lightweight PowerShell script that allows you to remove pre-installed apps, disable telemetry, as well as perform various other changes to declutter and c…...
从零开始:Java使用通用物体识别-ResNet18镜像实现图像分类
从零开始:Java使用通用物体识别-ResNet18镜像实现图像分类 你是否想过,用Java写几行代码,就能让程序看懂一张图片里有什么?过去,这可能需要搭建复杂的Python环境、学习深度学习框架、处理繁琐的模型部署。但现在&…...
