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

二分+ST表+递推,Cf 1237D - Balanced Playlist

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1237D - Codeforces


二、解题报告

1、思路分析

case3提示我们一件事情:如果存在某个位置永远不停止,那么所有位置都满足永远不停止

很容易证明

随着下标右移,区间最大值不会变大,那么后面2倍大于旧的最大值的数的二倍仍然大于新的最大值

那么对于每个位置我们要找到第一个满足a[i] < max / 2的 i

我们可以st表预处理出区间最大值最小值

然后对于递推求解ans

对于i,我们二分查找找到第一个大于a[i]的j,同样二分查找找到第一个a[k] < a[i]的k

如果k < j,那么显然答案就是j - i

否则, ans[i] = k - i + ans[k % N]

我们建立了递推关系,一共N个状态,每个状态O(log)转移,总体时间复杂度就是O(NlogN)

2、复杂度

时间复杂度: O(NlogN)空间复杂度:O(NlogN)

3、代码详解

 ​
#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;std::ostream& operator<< (std::ostream& out, i128 x) {std::string s;while (x) s += ((x % 10) ^ 48), x /= 10;std::reverse(s.begin(), s.end());return out << s;
}template<class T, int M>
struct ST {T n;std::vector<T> nums;std::vector<T> log2;std::vector<std::array<T, M>> f0, f1;ST (T _n, std::vector<T>& _nums): n(_n), nums(_nums), log2(_n + 1), f0(_n), f1(_n) {log2[2] = 1;for (int i = 3; i <= n; i ++ ) log2[i] = log2[i >> 1] + 1;for (int i = 0; i < n; i ++ ) f0[i][0] = f1[i][0] = nums[i];for (int j = 1; j < M; j ++ )for (int i = 0; i < n && i + (1 << (j - 1)) < n; i ++ )f0[i][j] = std::max(f0[i][j - 1], f0[i + (1 << (j - 1))][j - 1]), f1[i][j] = std::min(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);}std::array<T, 2> query(int l, int r) {int k = log2[r - l + 1];return { std::max(f0[l][k], f0[r - (1 << k) + 1][k]), std::min(f1[l][k], f1[r - (1 << k) + 1][k]) };}
};void solve() {int N;std::cin >> N;std::vector<int> a(N * 2);for (int i = 0; i < N; i ++ ) std::cin >> a[i], a[i + N] = a[i];ST<int, 18> st(N * 2, a);if (st.query(0, N - 1)[0] <= st.query(0, N - 1)[1] * 2LL) {for (int i = 0; i < N; i ++ ) std::cout << -1 << " \n"[i == N - 1];return;}std::vector<int> ans(N, -1);auto findmi = [&](int l, int r) -> int {int x = a[l - 1];while (l < r) {int mid = l + r >> 1;auto [ma, mi] = st.query(l, mid);if (mi * 2LL < x) r = mid;else l = mid + 1;}return l;};auto findma = [&](int l, int r) -> int {int x = a[l - 1];while (l < r) {int mid = l + r >> 1;auto [ma, mi] = st.query(l, mid);if (ma > x) r = mid;else l = mid + 1;}   return l;};auto dfs = [&](auto&& self, int x) -> int {if (~ans[x]) return ans[x];int lt = findmi(x + 1, x + N), gt = findma(x + 1, x + N);if (lt < gt) return ans[x] = lt - x;return ans[x] = gt - x + self(self, gt % N);};for (int i = 0; i < N; i ++ ) std::cout << dfs(dfs, i) << " \n"[i == N - 1];
}   int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}

相关文章:

二分+ST表+递推,Cf 1237D - Balanced Playlist

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 1237D - Codeforces 二、解题报告 1、思路分析 case3提示我们一件事情&#xff1a;如果存在某个位置永远不停止&#xff0c;那么所有位置都满足永远不停止 很容易证明 随着下标右移&#xff0c…...

被裁员不可怕,可怕的是你只会写代码!

“听说隔壁部门又要裁员了&#xff0c;人心惶惶的……” “是啊&#xff0c;这年头&#xff0c;工作真是越来越难了&#xff0c;谁知道下一个会不会是自己呢&#xff1f;” 这两天&#xff0c;公司里弥漫着一股紧张的气氛&#xff0c;裁员的消息&#xff0c;就像是一场突如其来…...

服务器之间的时间如何保证一致

服务器之间的时间一致性主要通过以下几种方法和技术来保证&#xff1a; NTP&#xff08;Network Time Protocol&#xff09;同步&#xff1a;这是最常见的时钟同步方法。NTP协议允许服务器从一个或多个时间服务器&#xff08;称为NTP服务器&#xff09;获取精确的时间信息&…...

算法体系-20 第二十节暴力递归到动态规划

前言 动态规划模型从尝试暴力递归到傻缓存到动态规划 四种模型和体系班两种模型一共六种模型 0.1 从左往右模型 0.2 范围讨论模型范围尝试模型 &#xff08;这种模型特别在乎讨论开头如何如何 结尾如何如何&#xff09; 玩家博弈问题&#xff0c;玩家玩纸牌只能那左或者右 0.3 …...

字符集相关变量理解

建表 创建一个新表&#xff0c;想让他的字符集是 gbk&#xff0c;怎么弄? 尝试1&#xff1a; 失败&#xff01;原因&#xff1a; set names gbk; 等价于&#xff1a;set character_set_client gbk; set character_set_connection gbk; set character_set_results gbk;尝…...

618哪些数码产品比较好?2024超高人气产品推荐!

随着6.18大促的脚步渐近&#xff0c;你是否已经按捺不住内心的激动&#xff0c;想要在网络购物的海洋中畅游&#xff0c;尽情享受购物的狂欢&#xff1f;然而&#xff0c;面对繁多的商品和各式各样的优惠活动&#xff0c;你是否感到了一丝迷茫&#xff1f;作为一位经验丰富的网…...

基础-01-计算机网络概论

一. 计算机网络的发展与分类 1.计算机网络的形成与发展 计算机网络&#xff1a;计算机技术与通信技术的结合 ICTITCT 2.计算机网络标准阶段 3.计算机网络分类1:通信子网和资源子网 通信子网:通信节点(集线器、交换机、路由器等)和通信链路(电话线、同轴电缆、无线电线路、卫…...

STM32学习笔记(一)--时钟树详解

&#xff08;1&#xff09;时钟概述&#xff1b;时钟是具有周期性的脉冲信号&#xff0c;最常用的是占空比50%的方波。&#xff08;时钟相当于单片机的脉搏&#xff1b;STM32本身非常复杂&#xff0c;外设非常的多&#xff0c;为了保持低功耗工作&#xff0c;STM32 的主控默认不…...

JAVA小知识16:JAVA常用的API

一、Math 方法名说明public static int abs(int a)获取参数绝对值public static double ceil(double a)向上取整public static double floor(double a)向下取整public static int round(float a)四舍五入public static int max(int a,int b)获取两个int值中的较大值public s…...

PaddleDetection快速体验quick_start

1 快速体验 # 设置显卡 export CUDA_VISIBLE_DEVICES0# 用PP-YOLO算法在COCO数据集上预训练模型预测一张图片 python tools/infer.py -c configs/ppyolo/ppyolo_r50vd_dcn_1x_coco.yml -o use_gputrue weightshttps://paddledet.bj.bcebos.com/models/ppyolo_r50vd_dcn_1x_coc…...

《Foundation CSS 参考手册》

《Foundation CSS 参考手册》 引言 Foundation 是一个强大的前端框架&#xff0c;它为开发者提供了一系列的CSS工具和组件&#xff0c;以便快速构建响应式、移动优先的网站。本参考手册旨在为那些希望深入了解和使用Foundation CSS的开发者提供一个全面的指南。 基础知识 1…...

方法递归-结合案例阶乘问题、求和问题和猴子吃桃问题

方法递归 递归是一种算法 在程序设计语言中广泛应用. 从形式上来说&#xff1a;方法调用自身的形式称为方法递归&#xff08;recursion&#xff09;. 递归的形式&#xff1a; 直接递归&#xff1a;方法调用自己。间接递归&#xff1a;方法调用其他方法&#xff0c;其他方法…...

有一个主域名跟多个二级子域名时该怎么申请SSL证书?

当您拥有主域名以及多个子域名时&#xff0c;选择合适的SSL证书类型对于确保网站的安全性至关重要。以下是三种SSL证书类型的简要介绍&#xff1a; 单域名SSL证书&#xff1a; 功能&#xff1a;只能绑定单个域名&#xff0c;无论是主域名还是子域名。 适用场景&#xff1a;仅…...

LabVIEW伺服电机可应用在哪些领域

LabVIEW与伺服电机的结合&#xff0c;得益于LabVIEW强大的图形编程能力和伺服电机的高精度、高响应速度&#xff0c;广泛应用于多个领域。以下是一些主要应用领域&#xff1a; 1. 工业自动化 数控机床控制 LabVIEW用于控制伺服电机在数控机床中的运动&#xff0c;实现高精度的…...

nvidia 显卡 没有正确安装或配置 OpenGL 库

看到这个错误可能意味着你的系统没有正确安装或配置 OpenGL 库。以下是一些步骤来解决这个问题&#xff1a; 1. 安装必要的软件包 确保你已经安装了必要的软件包&#xff0c;包括 mesa-utils 和 nvidia-driver。 安装 mesa-utils sudo apt update sudo apt install mesa-ut…...

将自己md文件发布到自己的博客园实现文件的持久化存储

上传markdown文件到博客园 目录 【0】需求原因【1】功能【2】环境【最佳实践测试】 &#xff08;1&#xff09;查看 Typora 设置&#xff08;2&#xff09;配置 pycnblog 配置文件 config.yaml&#xff08;3&#xff09;运行 pycnblog 中的文件 cnblog_markdown.cmd&#xff0…...

uni-app的生命周期(应用,页面生命周期)

1. uni-app的生命周期&#xff08;应用&#xff0c;页面生命周期&#xff09; 1.1. 应用生命周期 1.1.1. 定义在app.vue中 生命周期函数名说明onLaunch当uni-app 初始化完成时触发&#xff08;全局只触发一次&#xff09;onShow当 uni-app 启动&#xff0c;或从后台进入前台…...

响应式企业网站建站系统源码 模版丰富+一站式建站 全开源可二次开发 带源码包+搭建部署教程

系统概述 在数字化转型的浪潮中&#xff0c;企业官网作为品牌展示、产品推广及客户服务的重要窗口&#xff0c;其建设质量直接影响着企业的线上形象与市场竞争力。响应式企业网站建站系统源码的出现&#xff0c;为企业提供了一种高效、灵活且成本可控的建站解决方案。 代码示…...

如何解除内存卡的写保护并格式化为exFAT文件系统

最近有客户提问内存卡提示写保护&#xff0c;且无法格式化为exFAT格式的问题&#xff0c;可能是由于多种原因引起的。以下是一些可能的解决方法&#xff1a; 1. 检查物理写保护开关 一些SD卡和MicroSD卡适配器上有一个小的物理开关&#xff0c;可以启用或禁用写保护。确保这个…...

【 EI会议 | 西南大学主办 | 往届均已实现检索】第三届神经形态计算国际会议(ICNC 2024)

第三届神经形态计算国际会议&#xff08;ICNC 2024) 2024 3rd International Conference on Neuromorphic Computing (ICNC 2024) 一、重要信息 大会官网&#xff1a;www.ic-nc.org&#xff08;点击投稿/参会/了解会议详情&#xff09; 会议时间&#xff1a;2024年12月13-15…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...