【枚举区间+线段树】CF Ehu 152 E
Problem - E - Codeforces
题意:

思路:
感觉是个套路题
对区间计数,按照CF惯用套路,枚举其中一个端点,对另一个端点计数
对于这道题,枚举右端点,对左端点计数

Code:
#include <bits/stdc++.h>#define int long longusing i64 = long long;constexpr int N = 1e6 + 10;
constexpr int M = 1e6 + 10;
constexpr int P = 2600;
constexpr i64 Inf = 1e18;
constexpr int mod = 1e9 + 7;
constexpr double eps = 1e-6;struct Segtree {int val, lazy;
}tr[N << 2];int n;
int a[N];
int lmi[N], lmx[N];void pushup(int rt) {tr[rt].val = tr[rt << 1].val + tr[rt << 1 | 1].val;
}
void build(int rt, int l, int r) {if (l == r) {tr[rt].val = 0;tr[rt].lazy = -1;return;}int mid = l + r >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);pushup(rt);
}
void pushdown(int rt, int tot) {tr[rt << 1].lazy = tr[rt].lazy;tr[rt << 1 | 1].lazy = tr[rt].lazy;tr[rt << 1].val = (tot - tot / 2) * (tr[rt].lazy? 1 : 0);tr[rt << 1 | 1].val = (tot / 2) * (tr[rt].lazy? 1 : 0);tr[rt].lazy = -1;
}
void modify(int rt, int l, int r, int x, int y, int k) {if (x <= l && r <= y) {tr[rt].lazy = k;tr[rt].val = k * (r - l + 1);return;}if (tr[rt].lazy != -1) pushdown(rt, r - l + 1);int mid = l + r >> 1;if (x <= mid) modify(rt << 1, l, mid, x, y, k);if (y > mid) modify(rt << 1 | 1, mid + 1, r, x, y, k);pushup(rt);
}
void solve() {std::cin >> n;for (int i = 1; i <= n; i ++) {std::cin >> a[i];}std::stack<int> S, S2;for (int i = 1; i <= n; i ++) {while(!S.empty() && a[S.top()] >= a[i]) S.pop();lmi[i] = S.empty() ? 0 : S.top();S.push(i);}for (int i = 1; i <= n; i ++) {while(!S2.empty() && a[S2.top()] <= a[i]) S2.pop();lmx[i] = S2.empty() ? 0 : S2.top();S2.push(i);}build(1, 1, n);int ans = 0;for (int r = 1; r <= n; r ++) {if (lmi[r] + 1 <= r - 1) modify(1, 1, n, lmi[r] + 1, r - 1, 0);if (lmx[r] + 1 <= r - 1) modify(1, 1, n, lmx[r] + 1, r - 1, 1);ans += tr[1].val;}std::cout << ans << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while (t--) {solve();}return 0;
}
相关文章:
【枚举区间+线段树】CF Ehu 152 E
Problem - E - Codeforces 题意: 思路: 感觉是个套路题 对区间计数,按照CF惯用套路,枚举其中一个端点,对另一个端点计数 对于这道题,枚举右端点,对左端点计数 Code: #include &…...
宏定义天坑记录
宏定义天坑记录 事件原委与推理过程 在编译一个使用了Protobuf的项目时出现了如下报错 [ybVM-8-7-centos boost_searcher]$ make g -o http_server http_server.cc data/raw_html.pb.cc -stdc11 -lboost_system -lboost_filesystem -lpthread -ljsoncpp -lprotobuf In file…...
Git的一些常用概念与操作方法分享
Git是一个版本控制系统,它可以记录代码的变化历史并允许多个开发者同时对同一代码库进行开发。以下是Git的基本概念和使用方式: 仓库(Repository)- 保存代码的地方。Git仓库包含了所有的版本历史记录、代码以及其他相关文件。 分…...
webpack实战:某网站JS逆向分析
文章目录 1. 写在前面2. 抓包分析3. 扣加密代码 1. 写在前面 好的逆向能够帮助我们了解加密实现,然后根据加密方式(md5,base64,res,des,rsa…)还原加密算法的过程。可以看看我之前的这篇文章:快速定位查找加密方式特征与技巧 目标站点&#…...
826. 安排工作以达到最大收益;2257. 统计网格图中没有被保卫的格子数;816. 模糊坐标
826. 安排工作以达到最大收益 核心思想:排序维护最大利润。首先我们需要对工人按照能力排序,前面工人满足的最大利润后面的工人肯定是满足的,所以我们只需要用一个tmp来维护小于等于当前工人的最大利润,然后如何得到tmpÿ…...
JAVA毕业设计097—基于Java+Springboot+Vue+uniapp的医院挂号小程序系统(源码+数据库)
基于JavaSpringbootVueuniapp的医院挂号小程序系统(源码数据库)097 一、系统介绍 本系统前后端分离(网页端和小程序端都有) 本系统分为管理员、医院、用户三种角色(角色菜单可自行分配) 用户功能: 注册、登录、医院搜索、最新资讯、医生搜索、挂号预约、挂号记…...
4.3.3.1 【MySQL】CHAR(M)列的存储格式
我们知道 Compact 行格式在 CHAR(M) 类型的列中存储数据的时候还挺麻烦,分变长字符集和定长字符集的情况,而在 Redundant 行格式中十分干脆,不管该列使用的字符集是啥,只要是使用 CHAR(M) 类型,占用的真实数据空间就是…...
js 处理数组合并vs对象合并
前言: 前端开发中,我们会遇到各种数据的需求,但是后端给你返回的数据结构又不是你想要的, 只能自己动手,去组装数据,重新定义数据结构了。 1. js 数组合并的方法 常用的应该是 concat 方法. 示例: let arr1 […...
Webpack vs Vite的核心差异
构建速度: Webpack: Webpack的构建速度相对较慢,尤其在大型项目中,因为它需要分析整个依赖图,进行多次文件扫描和转译。Vite: Vite以开发模式下的极速构建著称。它利用ES模块的特性,只构建正在编辑的文件,而不是整个项…...
53、springboot对websocket的支持有两种方式-------1、基于注解开发 WebSocket ,简洁实现多人聊天界面
基于注解开发 WebSocket –注解就是: OnOpen、 OnClose 、 OnMessage 、OnError这些 ★ WebSocket的两种开发方式 ▲ Spring Boot为WebSocket提供了两种开发方式: 基于spring-boot-starter-websocket.jar开发WebSocket 基于Spring WebFlux开发WebSoc…...
18 Linux之Python定制篇-Python开发平台Ubuntu
18 Linux之Python定制篇-Python开发平台Ubuntu 文章目录 18 Linux之Python定制篇-Python开发平台Ubuntu18.1 安装Ubuntu虚拟机18.4 Ubuntu的root用户18.5 Ubuntu下开发Python 学习视频来自于B站【小白入门 通俗易懂】2021韩顺平 一周学会Linux。可能会用到的资料有如下所示&…...
AMEYA360:士兰微推出600A/1200V IGBT汽车驱动模块,提升充电速度与行驶动力
随着人们对环保意识的提高和汽车驾驶体验感的不断追求,新能源汽车的市场需求逐渐增大,已然成为汽车发展的大趋势,但是新能源汽车充电时间长、续航里程短等问题仍然是汽车厂商和车主们的痛点。因此,需要更好的汽车驱动产品来实现“…...
【Linux】Epoll Reactor【反应堆】模式的工作流程
Reactor模式的工作流程 主线程往epoll内核事件表中注册socket上的就绪事件。主线程调用epoll_wait等待socket上有数据可读。当socket上有数据可读时,epoll_wait通知主线程。主线程将socket可读事件放入请求队列。睡眠在请求队列上的某个工作线程被唤醒,…...
Php“梦寻”淘宝天猫商品详情数据接口,淘宝商品详情数据API接口,淘宝API接口申请指南(含代码示例)
淘宝商品详情接口 API 是开放平台提供的一种 API 接口,它可以帮助开发者获取淘宝商品的详细信息,包括商品的标题、描述、图片等信息。在淘宝电商平台的开发中,淘宝详情接口 API 是非常常用的 API,因此本文将详细介绍淘宝详情接口 …...
驱动轴相机参数设置Web前端界面开发
一、基于Django的Web应用界面的开发: 在Realtimeresults.html上添加一个按钮组件,获取检测到的轴型和车轮信息,点击后可以获取package.json里存放的json数据,效果如下: 实现逻辑:需要从URL设置、视图函数、…...
论文简读 LORA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS
论文地址:https://arxiv.org/pdf/2106.09685.pdf 项目地址:https://github.com/microsoft/LoRA 全文翻译地址:https://zhuanlan.zhihu.com/p/611557340 本来想自行翻译的,但最近没有空 1、关键凝练 1.1 LORA是什么? …...
23062网络编程day7
网络聊天室编写(基于UDP) 服务器 #include <myhead.h>#define PORT 8888 //端口号:接收方绑定的端口号 #define IP "192.168.114.56" //本机IP#define ERR_MSG(msg) do{\fprintf(stderr, "__%d__:&…...
Java面向对象学习笔记-2
前言 本文介绍了Java中类的定义和对象的创建的基本概念。我们通过示例代码演示了如何定义不同类型的类,包括管理员信息、顾客信息、学校信息和访客信息,并展示了如何创建这些类的对象以及如何访问它们的属性和方法。这些示例有助于理解面向对象编程的基…...
入栏需看——学习记忆
记忆方法千千种,本栏意在梳理其中道道来,旦有小得,肥肠幸耶。从不同角度分析学习记忆。 逻辑篇 有逻辑 用思维导图 思维导图记忆有逻辑的文本/内容 理论 巧记书本结构–思维导图 模仿 HCIE-Cloud Computing LAB备考第一步:…...
[C++]杨辉三角
目录 题目 解题思路 代码实现 获取数字 打印函数 主函数 全部代码 运行结果 题目 给定一个非负整数numRows ,生成「杨辉三角」的前numRows行。 在「杨辉三角」中,每个数是它左上方和右上方的数的和。 解题思路 第k列的第i个数字的值第k-1列的(…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
