CF1707E Replace
题目描述
给定一个长为 nnn 的序列 a1,…,ana_1,\ldots,a_na1,…,an,其中对于任意的 iii 满足 1≤ai≤n1 \leq a_i \leq n1≤ai≤n。
定义一个二元组函数如下:
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})(l≤r)
你需要回答 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=lr−1f((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=lr−1fk((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,其中对于任意的 iii 满足 1≤ai≤n1 \leq a_i \leq n1≤ai≤n。 定义一个二元组函数如下: 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)
作者:小萌新 专栏:Linux 作者简介:大二学生 希望能和大家一起进步! 本篇博客简介:介绍Linux的常用工具make/makefile git Linux项目自动化构建工具 – make/Makefile 背景 会不会写Makefile 从侧面说明了一个人是否具…...

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

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

项目介绍 + 定长内存池设计及实现
你好,我是安然无虞。 文章目录项目介绍当前项目做的是什么?技术栈内存池是什么?池化技术内存池内存池主要解决的问题malloc定长内存池学习目的定长内存池设计项目介绍 当前项目做的是什么? 这个项目是实现一个高并发的内存池, 它的原型是 Google 的一个开源项…...
Linux--线程安全的单例模式--自旋锁--0211
1. 线程安全的单例模式 1.1 什么是单例模式 某些类, 只应该具有一个对象(实例), 就称之为单例. 1.1.1 懒汉方式实现单例模式 以上篇博文的线程池为例 Liunx--线程池的实现--0208 09_Gosolo!的博客-CSDN博客 实现懒汉模式首先要先将构造函数私有化,…...

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

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

2023年浙江食品安全管理员考试真题题库及答案
百分百题库提供食品安全管理员考试试题、食品安全管理员考试预测题、食品安全管理员考试真题、食品安全管理员证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 一、判断题 7.(重点)《餐饮服务食品安全…...

Webstorm 代码没有提示,uniapp 标签报错
问题 项目是用脚手架创建的: vue create -p dcloudio/uni-preset-vue my-project 打开之后,添加view标签警告报错的。代码也没有提示,按官方说法: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.事务介绍 事务是一组操作的集合…...

Linux操作系统学习(了解环境变量)
文章目录环境变量初识除了上述介绍的PATH,还有一些常见的环境变量如:查看环境变量方法 :环境变量的基本概念:本地变量:环境变量初识 环境变量解释起来比较抽象,先看示例: #include <stdio.…...

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

C++:类和对象(下)
文章目录1 再谈构造函数1.1 构造函数体赋值1.2 初始化列表1.3 explicit关键字2 static成员2.1 概念2.2 特性3 友元3.1 友元函数(流插入(<<)及流提取(>>)运算符重载)3.2 友元类4 内部类5 匿名对…...
ASP.NET Core MVC 项目 AOP之IResultFilter和IAsyncResultFilter
目录 一:说明 二:IActionFilter同步 三:IAsyncActionFilter异步 一:说明 IResultFilter同步过滤器与IAsyncResultFilter异步过滤器常常被用作于渲染视图或处理结果。 IResultFilter同步过滤器执行顺序: 1:执行控制器中的构造函数,实例化控制器 2:执行具体的Acti…...

jstack排查cpu占用高[复习]
这样就可以看到占用CPU高的代码位置。 总结:就是先查到占用高的应用和具体的线程,然后根据线程到堆积信息查找即可。 不过堆栈信息非十进制,需提前把线程号转为十六进制。 这样就可以看到占用CPU高的代码位置。 总结:就是先查到…...

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

SpringBoot Mybatis 分页实战
pageInfo的属性 pageNum:当前页 pageSize:页面数据量 startRow:当前页首条数据为总数据的第几条 endRow:当前页最后一条数据为总数据的第几条 total:总数据量 pages:总页面数 listPage{}结果集 reasonable …...

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

Java多级缓存是为了解决什么的?
前言 提到缓存,想必每一位软件工程师都不陌生,它是目前架构设计中提高性能最直接的方式。 缓存技术存在于应用场景的方方面面。从网站提高性能的角度分析,缓存可以放在浏览器,可以放在反向代理服务器,还可以放…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...