当前位置: 首页 > news >正文

刷题记录:牛客NC54585小魂和他的数列 [线段树卡常,真恶心]

传送门:牛客

题目描述:

一天,小魂正和一个数列玩得不亦乐乎。
小魂的数列一共有n个元素,第i个数为Ai。
他发现,这个数列的一些子序列中的元素是严格递增的。
他想知道,这个数列一共有多少个长度为K的子序列是严格递增的。
请你帮帮他,答案对998244353取模。
对于100%的数据,1≤ n ≤ 500,000,2≤ K ≤ 10,1≤ Ai ≤ 109。
输入:
5 3
2 3 3 5 1
输出:
2

前置提要:本题卡线段树常数,十分恶心,本人试了几次卡常,只能优化到85分

首先看到题面,我们会发现这是一个比较清明的dpdpdp题.我们设dp[i][j]dp[i][j]dp[i][j]为以iii位置结尾长度为jjj的子序列的的个数.那么对于当前的i,ji,ji,j来说,我们的需要找到前i−1i-1i1个位置中每一个dp[k][j−1]k∈[1,i−1]&&a[k]<a[i]dp[k][j-1] \quad k\in[1,i-1] \&\& a[k]<a[i]dp[k][j1]k[1,i1]&&a[k]<a[i]然后进行累加,此时如果我们直接使用forforfor进行枚举会发现时间复杂度是不对的.此时复杂度达到了n∗k∗lognn*k*lognnklogn所以我们需要进行优化

我们可以用线段树树状数组来维护这个题目.开kkk线段树树状数组来维护i−1i-1i1之前所有位置子序列长度为lenlen∈[1,k]len \quad len\in[1,k]lenlen[1,k]的子序列个数.那么对于我们现在的dp[i][j]dp[i][j]dp[i][j]来说,dp[i][j]=query(j−1,1,i−1)参数(id,l,r)dp[i][j]=query(j-1,1,i-1) \quad 参数(id,l,r)dp[i][j]=query(j1,1,i1)参数(id,l,r).用ansansans累加一下即可

本题需要进行离散化操作

下面是本人优化到平常极限的线段树代码(85分):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 500100
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r,sum;
}tree[11][maxn*4];
const int mod=998244353;
inline void update(int id,int pos,int v,int l,int r,int rt) {if(l==pos&&r==pos) {tree[id][rt].sum=(tree[id][rt].sum+v)%mod;return ;}int mid=(l+r)>>1;if(pos<=mid) update(id,pos,v,l,mid,ls);else update(id,pos,v,mid+1,r,rs);tree[id][rt].sum=(tree[id][ls].sum+tree[id][rs].sum)%mod;
}
inline int query(int id,int l,int r,int L,int R,int rt) {if(L==l&&R==r) return tree[id][rt].sum;int mid=(L+R)>>1;if(r<=mid) return query(id,l,r,L,mid,ls);else if(l>mid) return query(id,l,r,mid+1,R,rs);else return (query(id,l,mid,L,mid,ls)+query(id,mid+1,r,mid+1,R,rs))%mod;
}
int n,k;int a[maxn];
int v[maxn];
int main() {n=read();k=read();for(int i=1;i<=n;i++){a[i]=read();v[i-1]=a[i];}sort(v,v+n);int Size=unique(v,v+n)-v;int ans=0;for(int i=1;i<=n;i++) {int x=lower_bound(v,v+Size,a[i])-v+1;update(1,x,1,1,Size,1);if(x-1==0) continue;for(int j=2;j<=k;j++) {if(j-1>i) continue;int sum=query(j-1,1,x-1,1,Size,1);if(j==k) ans=(ans+sum)%mod;update(j,x,sum,1,Size,1);}}cout<<ans<<endl;return 0;
}

下面是可以AC本题的树状数组代码(等我去学完立马补上,博主已简单过了一遍):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
const int mod=998244353;
inline int lowbit(int x) {return x&(~x+1);
}
int n,k;int a[maxn];int sum[11][maxn];
vector<int>v;
void add(int id,int pos,int v) {while(pos<=n) {sum[id][pos]=(sum[id][pos]+v)%mod;pos+=lowbit(pos);}
}
int query(int id,int pos) {int ans=0;while(pos) {ans=(ans+sum[id][pos])%mod;pos-=lowbit(pos);}return ans;
}
int main() {n=read();k=read();for(int i=1;i<=n;i++) {a[i]=read();v.push_back(a[i]);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int ans=0;for(int i=1;i<=n;i++) {int x=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;add(1,x,1);for(int j=2;j<=k;j++) {int sum=query(j-1,x-1);if(j==k) ans=(ans+sum)%mod;add(j,x,sum);}}cout<<ans<<endl;return 0;
}

相关文章:

刷题记录:牛客NC54585小魂和他的数列 [线段树卡常,真恶心]

传送门:牛客 题目描述: 一天&#xff0c;小魂正和一个数列玩得不亦乐乎。 小魂的数列一共有n个元素&#xff0c;第i个数为Ai。 他发现&#xff0c;这个数列的一些子序列中的元素是严格递增的。 他想知道&#xff0c;这个数列一共有多少个长度为K的子序列是严格递增的。 请你帮…...

2019蓝桥杯真题旋转 C语言/C++

题目描述 图片旋转是对图片最简单的处理方式之一&#xff0c;在本题中&#xff0c;你需要对图片顺时针旋转 90 度。 我们用一个 nm 的二维数组来表示一个图片&#xff0c;例如下面给出一个 34 的 图片的例子&#xff1a; 1 3 5 7 9 8 7 6 3 5 9 7 这个图片顺时针旋转 90 度…...

<JVM上篇:内存与垃圾回收篇>11 - 垃圾回收相关算法

对象存活判断 在堆里存放着几乎所有的 Java 对象实例&#xff0c;在 GC 执行垃圾回收之前&#xff0c;首先需要区分出内存中哪些是存活对象&#xff0c;哪些是已经死亡的对象。只有被标记为己经死亡的对象&#xff0c;GC 才会在执行垃圾回收时&#xff0c;释放掉其所占用的内存…...

狂飙Linux平台,软件部署大全

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…...

积分球原理及积分球类型介绍

标题积分球标准型积分球LED积分球均匀光源便携式高亮度积分球均匀光源微光积分球均匀光源积分球均匀光源iSphere高光谱响应光学积分球其他分类积分球 积分球原理:由于球体内整涂有白色漫反射材料的空腔球体&#xff0c;球壁上开有采样口&#xff0c;当待测样品光源进入积分球的…...

Vision Transformer(ViT) 2: 应用及代码讲解

文章目录1. 代码讲解1.1 PatchEmbed类1&#xff09;__init__ 函数2) forward 过程1.2 Attention类1&#xff09;__init__ 函数2&#xff09;forward 过程1.3 MLP类1&#xff09;__init__ 函数2&#xff09;forward函数1.4 Block类1&#xff09;__init__ 函数2&#xff09;forwa…...

高频面试题|JVM虚拟机的体系结构是什么样的?

一. 前言最近有很多小伙伴都在找工作&#xff0c;他们在面试时经常被面试官问到一个问题&#xff1a;请说说JVM虚拟机的体系结构是什么样的?很多小伙伴都能说出堆、栈等相关内容&#xff0c;但面试官紧接着又问&#xff0c;你还知道其他内容吗&#xff1f;这时不少小伙伴就语塞…...

MyBatis-Plus详细讲解(整合spring Boot)

哈喽&#xff0c;大家好&#xff0c;今天带大家了解的是MyBatis-Plus&#xff08;简称 MP&#xff09;&#xff0c;是一个 MyBatis 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生。首先说一下MyBatis-Plus的愿景是什么&…...

骨传导耳机是不是智商税?骨传导耳机真的不伤耳吗?

很多人对骨传导耳机是具有一定的了解&#xff0c;但是对骨传导耳机还是有一定的刻板印象&#xff0c;那么骨传导耳机到底是不是智商税呢&#xff1f;主要还是要从骨传导耳机传声原理上讨论。 骨传导耳机是属于固体传声的一种方式&#xff0c;通过骨骼传递声音&#xff0c;在使用…...

模拟实现string

目录 1、基本成员变量 2、默认成员函数 构造函数 析构函数 拷贝构造函数(深拷贝) 赋值运算符重载 3、容量与大小相关的函数 size capacity 4、字符串访问相关函数 operator [ ]重载 迭代器 5、增加的相关函数 reserve扩容 resize push_back追加字符 appe…...

自监督表征预训练之掩码图像建模

自监督表征预训练之掩码图像建模 前言 目前&#xff0c;在计算机视觉领域&#xff0c;自监督表征预训练有两个主流方向&#xff0c;分别是对比学习&#xff08;contrastive learning&#xff09;和掩码图像建模&#xff08;masked image modeling&#xff09;。两个方向在近几…...

华为OD机试题 - 磁盘容量(JavaScript)| 代码+思路+重要知识点

最近更新的博客 华为OD机试题 - 字符串加密(JavaScript) 华为OD机试题 - 字母消消乐(JavaScript) 华为OD机试题 - 字母计数(JavaScript) 华为OD机试题 - 整数分解(JavaScript) 华为OD机试题 - 单词反转(JavaScript) 使用说明 参加华为od机试,一定要注意不要完全背…...

ChatGPT:“抢走你工作的不会是 AI ,而是先掌握 AI 能力的人”

&#x1f497;wei_shuo的个人主页 &#x1f4ab;wei_shuo的学习社区 &#x1f310;Hello World &#xff01; ChatGPT&#xff1a;“抢走你工作的不会是 AI &#xff0c;而是先掌握 AI 能力的人” ChatGPT&#xff1a;美国OpenAI 研发的聊天机器人程序&#xff0c;人工智能技术…...

数据结构与算法(Java版) | 线性结构和非线性结构

之前&#xff0c;我们说过&#xff0c;数据结构是算法的基础&#xff0c;因此接下来在这一讲我就要来给大家重点介绍一下数据结构了。 首先&#xff0c;大家需要知道的是&#xff0c;数据结构包括两部分&#xff0c;即线性结构和非线性结构。知道这点之后&#xff0c;接下来我…...

电商数据查询平台:母婴行业妈妈用品全网热销,头部品牌格局初现

以往&#xff0c;奶粉、纸尿裤这类产品基本就代表了整体母婴市场中的消费品。而如今&#xff0c;随着母婴行业的高速发展和消费升级&#xff0c;母婴商品的种类日益丰富&#xff0c;需求也不断深入。 在京东平台&#xff0c;母婴大品类中除了包含婴童相关的食品&#xff08;奶粉…...

STM32模拟SPI协议获取24位模数转换(24bit ADC)芯片AD7791电压采样数据

STM32模拟SPI协议获取24位模数转换&#xff08;24bit ADC&#xff09;芯片AD7791电压采样数据 STM32大部分芯片只有12位的ADC采样性能&#xff0c;如果要实现更高精度的模数转换如24位ADC采样&#xff0c;则需要连接外部ADC实现。AD7791是亚德诺(ADI)半导体一款用于低功耗、24…...

华为OD机试题 - 交换字符(JavaScript)| 代码+思路+重要知识点

最近更新的博客 华为OD机试题 - 字符串加密(JavaScript) 华为OD机试题 - 字母消消乐(JavaScript) 华为OD机试题 - 字母计数(JavaScript) 华为OD机试题 - 整数分解(JavaScript) 华为OD机试题 - 单词反转(JavaScript) 使用说明 参加华为od机试,一定要注意不要完全背…...

最好的工程师像投资者一样思考,而不是建设者

我在大学期间住在图书馆。“我学习的教科书理论越多&#xff0c;我就会成为一名更好的工程师&#xff0c;”我想。然而&#xff0c;当我开始工作时&#xff0c;我注意到业内最优秀的工程师并不一定比应届毕业生了解更多的理论。他们只是带来了不同的心态&#xff0c;即投资者的…...

Mysql里的ibtmp1文件太大,导致磁盘空间被占满

目录 一、查看磁盘的时候发现磁盘空间100% 二、 排查的时候&#xff1a;查看是什么文件占用的时候&#xff0c;发现是数据库临时表空间增长的 三、为了避免以后再次出现ibtmp1文件暴涨&#xff0c;限制其大小&#xff0c;需在配置文件加入 四、重启Mysql实例&#xff08;重启后…...

android kotlin 协程(四) 协程间的通信

android kotlin 协程(四) 协程间的通信 学完本篇你将会了解到: channelproduceactorselect 先来通过上一篇的简单案例回顾一下挂起于恢复: fun main() {val waitTime measureTimeMillis {runBlocking<Unit> {println("main start") // 1 // …...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...