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

CF1707E Replace

题目描述

给定一个长为 nnn 的序列 a1,…,ana_1,\ldots,a_na1,,an,其中对于任意的 iii 满足 1≤ai≤n1 \leq a_i \leq n1ain

定义一个二元组函数如下:
f((l,r))=(min⁡{al,…,ar},max⁡{al,…,ar})(l≤r)f((l,r))=(\min\{a_l,\ldots,a_r\},\max\{a_l,\ldots,a_r\})(l \leq r)f((l,r))=(min{al,,ar},max{al,,ar})(lr)

你需要回答 qqq 次询问,每次给定 (li,ri)(l_i,r_i)(li,ri),问其最少经过多少次 fff 的调用(即 (l,r)→f((l,r))(l,r) \rightarrow f((l,r))(l,r)f((l,r)))使得 (li,ri)(l_i,r_i)(li,ri) 变成 (1,n)(1,n)(1,n),若无解请输出 -1

题解

智慧的性质题
首先注意到f((l,r))=⋃i=lr−1f((i,i+1))f((l,r))=\bigcup_{i=l}^{r-1}f((i,i+1))f((l,r))=i=lr1f((i,i+1))
发现可以推广到fk((l,r))=⋃i=lr−1fk((i,i+1))f^k((l,r))=\bigcup_{i=l}^{r-1}f^k((i,i+1))fk((l,r))=i=lr1fk((i,i+1)),可以用归纳法证明
接下来的做法就容易可以想出了
Fi,j=f2i((j,j+1))F_{i,j}=f^{2^i}((j,j+1))Fi,j=f2i((j,j+1)),然后倍增解决,合并区间可以用线段树,长度为111的线段需要特别处理

code\text{code}code

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
void read(int &res)
{res=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while('0'<=ch&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
}
const int N=1e5+100,B=40;
int n,q,a[N+10];
struct seg
{int l,r;
}f[B+10][N+10];
int g[B+10][N+10];
seg merge(seg a,seg b){return (seg){min(a.l,b.l),max(a.r,b.r)};}
struct SEG
{seg t[N<<2|1];#define ls (p<<1)#define rs (p<<1|1)#define mid ((l+r)>>1)void build(seg *f,int p=1,int l=1,int r=n-1){if(l==r){t[p]=f[l];return;}build(f,ls,l,mid),build(f,rs,mid+1,r);t[p]=merge(t[ls],t[rs]);}seg query(int L,int R,int p=1,int l=1,int r=n-1){if(L<=l&&r<=R) return t[p];if(R<=mid) return query(L,R,ls,l,mid);else if(L>mid) return query(L,R,rs,mid+1,r);else return merge(query(L,R,ls,l,mid),query(L,R,rs,mid+1,r));}#undef ls#undef rs#undef mid
}t[B+10];
int main()
{
//	freopen("a.in","r",stdin);read(n),read(q);if(n==1){for(;q--;) printf("0\n");return 0;}for(int i=1;i<=n;i++) read(a[i]);for(int i=1;i<n;i++) f[0][i]=(seg){min(a[i],a[i+1]),max(a[i],a[i+1])},g[0][i]=a[i];t[0].build(f[0]);for(int j=1;j<=B;j++){for(int i=1;i<n;i++){if(f[j-1][i].l==f[j-1][i].r) f[j][i]=(seg){g[j-1][f[j-1][i].l],g[j-1][f[j-1][i].l]};else f[j][i]=t[j-1].query(f[j-1][i].l,f[j-1][i].r-1);}t[j].build(f[j]);for(int i=1;i<=n;i++) g[j][i]=g[j-1][g[j-1][i]];}for(int l,r;q--;){read(l),read(r);if(l==1&&r==n){printf("0\n");continue;}ll ans=0;if(l!=r)for(int i=B;i>=0;i--){seg tmp=t[i].query(l,r-1);if(tmp.l!=1||tmp.r!=n){l=tmp.l,r=tmp.r;ans+=(1ll<<i);}if(l==r) break;}if(l==r) printf("-1\n");else{seg tmp=t[0].query(l,r-1);if(tmp.l==1&&tmp.r==n) printf("%lld\n",ans+1);else printf("-1\n");}}return 0;
}

相关文章:

CF1707E Replace

题目描述 给定一个长为 nnn 的序列 a1,…,ana_1,\ldots,a_na1​,…,an​&#xff0c;其中对于任意的 iii 满足 1≤ai≤n1 \leq a_i \leq n1≤ai​≤n。 定义一个二元组函数如下&#xff1a; f((l,r))(min⁡{al,…,ar},max⁡{al,…,ar})(l≤r)f((l,r))(\min\{a_l,\ldots,a_r\}…...

【Hello Linux】Linux工具介绍 (make/makefile git)

作者&#xff1a;小萌新 专栏&#xff1a;Linux 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;介绍Linux的常用工具make/makefile git Linux项目自动化构建工具 – make/Makefile 背景 会不会写Makefile 从侧面说明了一个人是否具…...

享元模式flyweight

享元模式属于结构型模式。享元模式是池技术的重要实现方式&#xff0c;它可以减少重复对象的创建&#xff0c;使用缓存来共享对象&#xff0c;从而降低内存的使用。细粒度的对象其状态可以分为两种&#xff1a;内部状态和外部状态。应用场景系统存在大量相似或相同的对象。外部…...

Pulsar

一、简介Apache Pulsar是Apache软件基金会顶级项目&#xff0c;是下一代云原生分布式消息流平台&#xff0c;集消息、存储、轻量化函数式计算为一体&#xff0c;采用计算与存储分离架构设计&#xff0c;支持多租户、持久化存储、多机房跨区域数据复制&#xff0c;具有强一致性、…...

项目介绍 + 定长内存池设计及实现

你好&#xff0c;我是安然无虞。 文章目录项目介绍当前项目做的是什么?技术栈内存池是什么?池化技术内存池内存池主要解决的问题malloc定长内存池学习目的定长内存池设计项目介绍 当前项目做的是什么? 这个项目是实现一个高并发的内存池, 它的原型是 Google 的一个开源项…...

Linux--线程安全的单例模式--自旋锁--0211

1. 线程安全的单例模式 1.1 什么是单例模式 某些类, 只应该具有一个对象(实例), 就称之为单例. 1.1.1 懒汉方式实现单例模式 以上篇博文的线程池为例 Liunx--线程池的实现--0208 09_Gosolo&#xff01;的博客-CSDN博客 实现懒汉模式首先要先将构造函数私有化&#xff0c;…...

图文解说S参数(进阶篇)

S参数是RF工程师/SI工程师必须掌握的内容&#xff0c;业界已有多位大师写过关于S参数的文章&#xff0c;即便如此&#xff0c;在相关领域打滚多年的人&#xff0c; 可能还是会被一些问题困扰着。你懂S参数吗? 图文解说S参数&#xff08;基础篇&#xff09; 请继续往下看...台湾…...

Sentinel源码阅读

基础介绍 Sentinel 的使用可以分为两个部分: 核心库&#xff08;Java 客户端&#xff09;&#xff1a;不依赖任何框架/库&#xff0c;能够运行于 Java 8 及以上的版本的运行时环境&#xff0c;同时对 Dubbo / Spring Cloud 等框架也有较好的支持&#xff08;见 主流框架适配&…...

2023年浙江食品安全管理员考试真题题库及答案

百分百题库提供食品安全管理员考试试题、食品安全管理员考试预测题、食品安全管理员考试真题、食品安全管理员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 一、判断题 7.&#xff08;重点&#xff09;《餐饮服务食品安全…...

Webstorm 代码没有提示,uniapp 标签报错

问题 项目是用脚手架创建的&#xff1a; vue create -p dcloudio/uni-preset-vue my-project 打开之后&#xff0c;添加view标签警告报错的。代码也没有提示&#xff0c;按官方说法&#xff1a;CLI 工程默认带了 uni-app 语法提示和 5App 语法提示。 但是我这里就是有问题。…...

MySQL-Innodb引擎事务原理

文章目录1.事务介绍2 事务特性3. 事务的实现原理4 redo log 保证持久性5 undo log 保证原子性6 MVCC 概念6.1 隐藏字段6.2 版本链6.3 ReadView6.3.1readview 版本控制规则7 隔离性 实现7.2 隔离性- REPEATABLE READ 可重复读下8 一致性1.事务介绍 事务是一组操作的集合&#xf…...

Linux操作系统学习(了解环境变量)

文章目录环境变量初识除了上述介绍的PATH&#xff0c;还有一些常见的环境变量如&#xff1a;查看环境变量方法 &#xff1a;环境变量的基本概念&#xff1a;本地变量&#xff1a;环境变量初识 环境变量解释起来比较抽象&#xff0c;先看示例&#xff1a; #include <stdio.…...

数据分析思维(六)|循环/闭环思维

循环/闭环思维 1、概念 在很多的分析场景下&#xff0c;我们需要按照一套流程反复分析&#xff0c;而不是进行一次性的分析&#xff0c;也就是说这套流程的结果会成为该流程的新一次输入&#xff0c;从而形成一个闭环&#xff0c;此时的分析思维我们称之为循环/闭环思维。 常…...

C++:类和对象(下)

文章目录1 再谈构造函数1.1 构造函数体赋值1.2 初始化列表1.3 explicit关键字2 static成员2.1 概念2.2 特性3 友元3.1 友元函数&#xff08;流插入&#xff08;<<&#xff09;及流提取&#xff08;>>&#xff09;运算符重载&#xff09;3.2 友元类4 内部类5 匿名对…...

ASP.NET Core MVC 项目 AOP之IResultFilter和IAsyncResultFilter

目录 一:说明 二:IActionFilter同步 三:IAsyncActionFilter异步 一:说明 IResultFilter同步过滤器与IAsyncResultFilter异步过滤器常常被用作于渲染视图或处理结果。 IResultFilter同步过滤器执行顺序: 1:执行控制器中的构造函数,实例化控制器 2:执行具体的Acti…...

jstack排查cpu占用高[复习]

这样就可以看到占用CPU高的代码位置。 总结&#xff1a;就是先查到占用高的应用和具体的线程&#xff0c;然后根据线程到堆积信息查找即可。 不过堆栈信息非十进制&#xff0c;需提前把线程号转为十六进制。 这样就可以看到占用CPU高的代码位置。 总结&#xff1a;就是先查到…...

网络安全-Pyhton环境搭建

网络安全-Pyhton环境搭建 https://www.kali.org/get-kali/#kali-installer-images—kali官网下载地址 python这个东东呢 是目前来说最简单&#xff0c;方便的开源的脚本语言 广泛用于Web开发&#xff0c;AI&#xff0c;网站开发等领域 python要装2和3 为什么要安装两个版本…...

SpringBoot Mybatis 分页实战

pageInfo的属性 pageNum&#xff1a;当前页 pageSize&#xff1a;页面数据量 startRow&#xff1a;当前页首条数据为总数据的第几条 endRow&#xff1a;当前页最后一条数据为总数据的第几条 total&#xff1a;总数据量 pages&#xff1a;总页面数 listPage{}结果集 reasonable …...

计算机断层扫描结肠镜和全自动骨密度仪在一次检查中的可行性

计算机断层扫描结肠镜和全自动骨密度仪在一次检查中的可行性 Feasibility of Simultaneous Computed Tomographic Colonography and Fully Automated Bone Mineral Densitometry in a Single Examination 简单总结&#xff1a; 数据&#xff1a;患者的结肠镜检查和腹部CT检查…...

Java多级缓存是为了解决什么的?

前言   提到缓存&#xff0c;想必每一位软件工程师都不陌生&#xff0c;它是目前架构设计中提高性能最直接的方式。   缓存技术存在于应用场景的方方面面。从网站提高性能的角度分析&#xff0c;缓存可以放在浏览器&#xff0c;可以放在反向代理服务器&#xff0c;还可以放…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...