二分+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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/705001.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

YOLOv10原理与实战训练自己的数据集

课程链接&#xff1a;YOLOv10原理与实战训练自己的数据集_在线视频教程-CSDN程序员研修院 YOLOv10是最近提出的YOLO的改进版本。在后处理方面&#xff0c;提出了一致性双重分配策略用于无NMS训练&#xff0c;从而实现了高效的端到端检测。在模型架构方面&#xff0c;引入了全面…

Ubuntu安装opendaylight控制器

目录 实验任务 实验环境 安装过程&#xff1a; 将opendaylight添加到环境变量中 实验任务 在虚拟机1中安装opendaylight控制器并安装相应的组件在虚拟机2中使用mininet创建一个测试拓扑并将控制器的地址指向虚拟机1在虚拟机1中的opendaylight的web界面可以查看到创建的拓扑将…

实践分享:鸿蒙跨平台开发实例

先来理解什么是跨平台 提到跨平台&#xff0c;要先理解什么是“平台”&#xff0c;这里的平台&#xff0c;就是指应用程序的运行环境&#xff0c;例如操作系统&#xff0c;或者是Web浏览器&#xff0c;具体的像HarmonyOS、Android、iOS、或者浏览器&#xff0c;都可以叫做平台…

[vue2]深入理解路由

本节目标 单页应用程序路由概念VueRouter基本使用组件分类存放路由模块封装声明式导航其他路由配置路由模式编程式导航案例-面经基础版 单页应用程序 单页应用程序(SPA): 所有的功能都在一个HTML页面上实现 网易云音乐: 网易云音乐 多页应用程序(MPA): 不同功能通过切换不同…

透平油氧化安定性检测 发动机油运动粘度40℃检测

透平油氧化安定性检测 透平油&#xff0c;也称为涡轮机油或汽轮机油&#xff0c;是专门用于汽轮机的润滑油。它具有良好的抗氧化安定性和抗乳化性能&#xff0c;主要用于发电厂蒸气轮机、水电站水轮发电机以及其他需要深度精细润滑的场合。透平油的氧化安定性是衡量其在高温条件…

CentOs7 安装mysql5.7

1.卸载原系统中的mariadb…… 首先执行命令rpm -qa|grep mariadb查看是否有mariadb的安装包&#xff0c;没有可以不管 接下来&#xff0c;执行 rpm -e --nodeps mariadb-libs #删除掉下载mysql5.7安装包 1.前往官方网站复制yum源链接Mysql官网 然后鼠标右键粘贴 wget 执行…

极限网关助力好未来 Elasticsearch 容器化升级

极限网关在好未来的最佳实践案例&#xff0c;轻松扛住日增百 TB 数据的流量&#xff0c;助力 ES 从物理机到云原生架构的改造&#xff0c;实现了流控、请求分析、安全管理、无缝迁移等场景。一次完美的客户体验~ 背景 物理机架构时代 2022 年&#xff0c;好未来整个日志 Elas…

【云计算】Docker部署Nextcloud网盘并实现随地公网远程访问

配置文件 切换root权限&#xff0c;新建一个nextcloud的文件夹&#xff0c;进入该目录&#xff0c;创建docker-compose.yml [cpslocalhost ~]$ su root Password: 666666 [rootlocalhost cps]# ls Desktop Documents Downloads Music Pictures Public Templates Vide…

为CAP面板添加简单的Authentication登录验证功能 C#|.net

终于搞定了CAP Dashboard的登录验证功能! 因为网上找不到简单的CAP Dashboard的登录验证功能,所以这个功能摸索着开发了好久。 这个Authentication认证功能,不仅适用于CAP面板,也适用于懒得开发登录页面,但是又需要简单用户名密码登录的网页。 做过后端的比较熟悉,CAP面…

Science Advances|全溶液工艺制备超柔性有机光电器件(柔性电子/柔性传感/可穿戴电子/电子皮肤/有机光电器件)

2024年4月10日,日本东京大学Takao Someya和日本理化学研究所(RIKEN)Kenjiro Fukuda课题组,在《Science Advances》上发布了一篇题为“All-solution-processed ultraflexible wearable sensor enabled with universal trilayer structure for organic optoelectronic device…

TiKV 源码分析之 PointGet

作者&#xff1a;来自 vivo 互联网存储研发团队-Guo Xiang 本文介绍了TiDB中最基本的PointGet算子在存储层TiKV中的执行流程。 一、背景介绍 TiDB是一款具有HTAP能力(同时支持在线事务处理与在线分析处理 )的融合型分布式数据库产品&#xff0c;具备水平扩容或者缩容等重要特…

计算机网络知识点(三)

目录 一、简述TCP连接和关闭的状态转移 二、简述TCP慢启动 三、简述TCP如何保证有序 四、简述TCP常见的拥塞控制算法 五、简述TCP超时重传 一、简述TCP连接和关闭的状态转移 状态转移图 图中上半部分是TCP的三次握手过程的状态变迁&#xff0c;下半部分是TCP四次挥手过程的…

Three.js动效(第17辑):可视化大屏中炫酷的例子效果,如何实现

Hi&#xff0c;前几天分享了一些炫酷的例子动画背景图&#xff0c;很多老铁在评论区问我是如何实现的&#xff0c;10经验的前端开发和UI设计老司机→贝格前端工场&#xff0c;为您分享。 之前的文章&#xff1a;背景图的动效&#xff0c;非常的炫酷&#xff0c;非一般的感觉。…

el-table有横向滚动条时,最后一行数据被横向滚动条遮挡,且不出现纵向滚动条;只有当鼠标移到fixed列才能纵向滚动,移到非fixed列无法纵向滚动。

问题背景 项目使用的vue2&#xff0c;el-table有横向滚动条时&#xff0c;最后一行数据被横向滚动条遮挡&#xff0c;且不出现纵向滚动条&#xff1b;只有当鼠标移到fixed列才能纵向滚动&#xff0c;移到非fixed列无法纵向滚动。 见下图&#xff1a;最后一行被遮挡住了一部分…

R语言ggHoriPlot包绘制地平线图

数据和代码获取&#xff1a;请查看主页个人信息&#xff01;&#xff01;&#xff01; 关键词“地平线图” 1. 数据读取与处理 首先&#xff0c;从TSV文件中读取数据&#xff0c;并进行数据清洗和处理。 rm(listls()) pacman::p_load(tidyverse,ggalt,ggHoriPlot,hrbrthemes…

python接入汇率换算工具提高网站/小程序日活度

实时汇率换算工具可以帮助用户快速准确地计算不同货币之间最新的汇兑比例。无论是金融从业者或者是人们日常生活出行都会使用到&#xff0c;广泛用于国际结算、银行汇率查询应用、开展跨国贸易、投资等参考场景。 我们可以通过在网站或者小程序中接入这样一个小工具&#xff0…

【个人博客搭建】(23)购买服务器、域名、备案

1、服务器主要是为了有一个公网的IP地址&#xff0c;方便我们可以通过网络随时访问 2、域名是对IP地址的一个替代。简单说IP地址可能不方便记忆&#xff0c;但是自己配置的域名会简单些&#xff0c;另外暴露IP地址也不安全。(虽然也能通过域名找到IP) 3、备案。这是政策。简单所…

工业企业的物料主数据管理应该如何做?

前言&#xff1a;如果我们说主数据是企业的“黄金数据”&#xff0c;那么对于制造型企业来说物料主数据就是企业的“钻石”数据。物料主数据贯穿于制造型企业的设计、工艺、采购、生产、库存、物流、销售的各个环节。做好物料主数据管理&#xff0c;是企业保有竞争力的关键&…

【Python】已解决报错 TypeError: Missing 1 Required Positional Argument

本文摘要&#xff1a;【Python】使用 Python 中将字符串转换为数组&#xff0c;并总结提出了几种可用方案。 &#x1f60e; 作者介绍&#xff1a;我是程序员洲洲&#xff0c;一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博…

Nginx06-rewrite模块详解与实验

目录 写在前面Nginx06nginx rewriterewrite 模块return案例01 访问/admin/ 返回403案例02 域名间跳转 if案例03 只允许GET、POST请求&#xff0c;其他禁止访问 set案例04 设置是否处于维护状态&#xff0c;是则返回503&#xff0c;否则正常访问 rewrite案例05 域名跳转案例06 r…