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

【51nod 连续区间】 题解(序列分治)

题目描述

       区间内的元素元素排序后 任意相邻两个元素值差为 1 1 1 的区间称为“连续区间”。
       如 3 , 1 , 2 3,1,2 3,1,2 是连续区间, 3 , 1 , 4 3,1,4 3,1,4 不是连续区间。
       给出一个 1 ∼ n 1 \sim n 1n 的排列,问有多少连续区间。
       n ≤ 1 0 6 n \leq 10^6 n106

分析

       我们考虑对序列分治,设 s o l v e ( l , r ) solve(l,r) solve(l,r) 表示左右端点在区间 [ l , r ] [l, r] [l,r] 内的 “连续区间” 的数量。那么显然, 有:

       s o l v e ( l , r ) = s o l v e ( l , m i d ) + s o l v e ( m i d + 1 , r ) + c a l c ( l , r , m i d ) solve(l, r) = solve(l, mid) + solve(mid + 1, r) + calc(l,r, mid) solve(l,r)=solve(l,mid)+solve(mid+1,r)+calc(l,r,mid)

       其中 c a l c ( l , r , m i d ) calc(l, r, mid) calc(l,r,mid) 表示左端点在 [ l , m i d ] [l, mid] [l,mid], 右端点在 [ m i d + 1 , r ] [mid + 1, r] [mid+1,r] 的 “连续区间” 数量。

       我们接下来考虑如何在 O ( l e n ) O(len) O(len) 的时间复杂度计算 c a l c ( l , r , m i d ) calc(l, r, mid) calc(l,r,mid)

       因为给的序列是 排列,所以有一个性质:对于一个连续区间而言,设它的长度是 k k k,那么有 m a x − m i n + 1 = k max - min + 1= k maxmin+1=k,即最大值减最小值等于区间长度。

       我们考虑区间 [ i , j ] [i, j] [i,j] 是否为合法区间,其中 i ∈ [ l , m i d ] , j ∈ [ m i d + 1 , r ] i \in [l, mid],j \in [mid + 1, r] i[l,mid]j[mid+1,r]

       设
       m a x x i = m a x ( a i , a i + 1 , a i + 2 , . . . , a m i d ) maxx_i = max(a_i, a_{i + 1}, a_{i + 2},..., a_{mid}) maxxi=max(ai,ai+1,ai+2,...,amid)
       m i n x i = m i n ( a i , a i + 1 , a i + 2 , . . . , a m i d ) minx_i = min(a_i, a_{i + 1}, a_{i + 2},..., a_{mid}) minxi=min(ai,ai+1,ai+2,...,amid)
       m a x x j = m a x ( a j , a j − 1 , a j − 2 , . . . , a m i d + 1 ) maxx_j = max(a_j, a_{j - 1}, a_{j - 2}, ..., a_{mid + 1}) maxxj=max(aj,aj1,aj2,...,amid+1)
       m i n x j = m i n ( a j , a j − 1 , a j − 2 , . . . , a m i d + 1 ) minx_j = min(a_j, a_{j - 1}, a_{j - 2}, ..., a_{mid + 1}) minxj=min(aj,aj1,aj2,...,amid+1)

       如果区间 [ l , r ] [l, r] [l,r]合法,那么有 m a x ( m a x x i , m a x x j ) − m i n ( m i n x i , m i n x j ) + 1 = j − i + 1 max(maxx_i, maxx_j) - min(minx_i, minx_j) + 1= j - i + 1 max(maxxi,maxxj)min(minxi,minxj)+1=ji+1
       把左右加 1 1 1 消掉,得到 m a x ( m a x x i , m a x x j ) − m i n ( m i n x i , m i n x j ) = j − i max(maxx_i, maxx_j) - min(minx_i, minx_j) = j - i max(maxxi,maxxj)min(minxi,minxj)=ji

       我们现在只考虑 m a x ( m a x i , m a x j ) max(max_i, max_j) max(maxi,maxj) 等于 m a x i max_i maxi 的情况。另一种情况可以把序列反转后做同样的统计。

       那么现在还可以再分两种情况:

       1 1 1. m i n ( m i n x i , m i n x j ) = m i n x i min(minx_i, minx_j) = minx_i min(minxi,minxj)=minxi:这一种情况我们可以枚举 i i i,然后根据 m a x x i maxx_i maxxi m i n x x i minxx_i minxxi 的大小算出来一个 j j j,然后检验一下是否满足 m i d + 1 ≤ j ≤ r mid + 1\leq j \leq r mid+1jr 以及 是否满足 m a x x j < m a x x i maxx_j < maxx_i maxxj<maxxi 并且 m i n x j > m i n x i minx_j > minx_i minxj>minxi 即可。计算和检验的复杂度都是 O ( 1 ) O(1) O(1) 的。

       2 2 2. m i n ( m i n x i , m i n x j ) = m i n x j min(minx_i, minx_j) = minx_j min(minxi,minxj)=minxj:那么不难发现, 如果 [ i , j ] [i, j] [i,j] 合法,需要满足 :

       m a x x i − m i n x j = j − i ⇒ m a x x i + i = m i n x j + j maxx_i - minx_j = j - i \Rightarrow maxx_i + i = minx_j + j maxximinxj=jimaxxi+i=minxj+j

       因为 m i n x j + j minx_j + j minxj+j 是一个定值, 可以开 记录数量。我们从 m i d mid mid l l l 枚举 i i i, 那么 m a x x i maxx_i maxxi 是不降的, m i n x i minx_i minxi 是不增的。那么由于需要满足 m a x x i > m a x x j maxx_i > maxx_j maxxi>maxxj 并且 m i n x i > m i n x j minx_i > minx_j minxi>minxj,所以我们考虑这两个限制条件相当于是给 j j j 的选择划定了一个范围。

       具体来讲,我们维护一个双指针 l t lt lt r t rt rt。表示在 枚举到 i i i j j j 的范围。 m a x x i maxx_i maxxi 增大那么 r t rt rt 向右移动,在桶里面让 m i n x r t + r t minx_{rt} + rt minxrt+rt 的位置加 1 1 1 m i n x i minx_i minxi 减小那么让 l t lt lt 向右移动,同时在桶里面让 m i n x l t + l t minx_{lt} + lt minxlt+lt 的位置减 1 1 1。指针稳定后统计 桶里面 m a x x i + i maxx_i + i maxxi+i 位置的数量就好了。

       复杂度计算十分典型:
       最多递归 l o g 2 n log_2n log2n 层,每一层的总复杂度是 O ( n ) O(n) O(n)。所以算法复杂度是 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)。可能带点常数。

       代码不难写。

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
inline int read(){int x = 0, f = 1; char c = getchar();while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
int n, a[N], b[N], minx[N], maxx[N], barrel[N * 2];
LL res;
LL get(int l, int r, int k){//k是中间点,属于左边  算左边为主导的答案 maxx[k] = minx[k] = b[k]; maxx[k + 1] = minx[k + 1] = b[k + 1];for(int i = k - 1; i >= l; i--){maxx[i] = max(maxx[i + 1], b[i]);minx[i] = min(minx[i + 1], b[i]);}for(int i = k + 2; i <= r; i++){maxx[i] = max(maxx[i - 1], b[i]);minx[i] = min(minx[i - 1], b[i]);}LL ans = 0;for(int i = k; i >= l; i--){// 首先算左边既有最大,又有最小的答案 int rt = maxx[i] - minx[i] + i;if(rt > r || rt <= k) continue;if(maxx[rt] < maxx[i] && minx[rt] > minx[i]) ans++;}int rt = k + 1, lt = k + 1;for(int i = k; i >= l; i--){// 接下来算左边有最大值,右边有最小值的答案 while(maxx[i] > maxx[rt] && rt <= r){barrel[minx[rt] + rt]++;rt++;}while(minx[i] < minx[lt] && lt < rt){barrel[minx[lt] + lt]--;lt++;}ans += barrel[maxx[i] + i];}for(int i = k + 1; i <= r; i++) barrel[minx[i] + i] = 0;return ans;
}
void solve(int l, int r){if(l == r){res++; return ;}int mid = (l + r >> 1);solve(l, mid); solve(mid + 1, r);// 算出来左右两边的答案 for(int i = l; i <= r; i++) b[i] = a[i];res += get(l, r, mid);reverse(b + l, b + r + 1);res += get(l, r, l + r - mid - 1);
}
int main(){n = read();for(int i = 1; i <= n; i++)a[i] = read();solve(1, n);printf("%lld\n", res);return 0;
}

相关文章:

【51nod 连续区间】 题解(序列分治)

题目描述 区间内的元素元素排序后 任意相邻两个元素值差为 1 1 1 的区间称为“连续区间”。 如 3 , 1 , 2 3,1,2 3,1,2 是连续区间&#xff0c; 3 , 1 , 4 3,1,4 3,1,4 不是连续区间。 给出一个 1 ∼ n 1 \sim n 1∼n 的排列&#xff0c;问有多少连续区间。 …...

10.30校招 实习 内推 面经

绿*泡*泡&#xff1a; neituijunsir 交流裙 &#xff0c;内推/实习/校招汇总表格 1、校招&#xff5c;极目智能2024届校招 校招&#xff5c;极目智能2024届校招 2、校招&#xff5c;杭州极弱磁场国家重大科技基础设施研究院2024秋季校园招聘正式启动&#xff01; 校招&…...

相比typescript,python的动态类型有什么优缺点?

以下是Python的动态类型相对于TypeScript的静态类型的一些优缺点&#xff1a; 1、Python的动态类型优点&#xff1a; 更灵活&#xff1a;Python的动态类型允许你在运行时更灵活地改变变量的类型&#xff0c;这对于快速原型设计和快速开发非常有帮助。 代码更简洁&#xff1a;…...

高效处理文件:批量顺序编号重命名方法

每个人都面临着文件管理的挑战&#xff0c;特别是那些需要处理大量文件的人。如何高效地管理这些文件一直是一个难题。为了解决这个问题&#xff0c;我向大家推荐一款强大的文件管理工具——固乔文件管家。这个工具可以帮助你快速有效地给文件进行批量重命名和编号&#xff0c;…...

JAVA深化篇_29—— 线程使用之线程联合以及Thread类中的其他常用方法【附有详细说明及代码案例】

线程联合 当前线程邀请调用方法的线程优先执行&#xff0c;在调用方法的线程执行结束之前&#xff0c;当前线程不能再次执行。线程A在运行期间&#xff0c;可以调用线程B的join()方法&#xff0c;让线程B和线程A联合。这样&#xff0c;线程A就必须等待线程B执行完毕后&#xf…...

〖Python网络爬虫实战㊲〗- JavaScript 逆向实战(一)

订阅:新手可以订阅我的其他专栏。免费阶段订阅量1000+python项目实战 Python编程基础教程系列(零基础小白搬砖逆袭) 说明:本专栏持续更新中,订阅本专栏前必读关于专栏〖Python网络爬虫实战〗转为付费专栏的订阅说明作者:爱吃饼干的小白鼠。Python领域优质创作者,2022年度…...

2023辽宁省数学建模A题铁路车站的安全标线完整原创论文详细讲解(含matlab代码)

大家好呀&#xff0c;从发布赛题一直到现在&#xff0c;总算完成了辽宁省数学建模A题完整的成品论文。 本论文可以保证原创&#xff0c;保证高质量。绝不是随便引用一大堆模型和代码复制粘贴进来完全没有应用糊弄人的垃圾半成品论文。 B预计下午两点前更新完毕&#xff0c;A全…...

(14)学习笔记:动手深度学习(Pytorch神经网络基础)

文章目录 神经网络的层与块块的基本概念自定义块 问答 神经网络的层与块 块的基本概念 以多层感知机为例&#xff0c; 整个模型接受原始输入&#xff08;特征&#xff09;&#xff0c;生成输出&#xff08;预测&#xff09;&#xff0c; 并包含一些参数&#xff08;所有组成层…...

Leetcode-1 两数之和

暴力穷举 class Solution {public int[] twoSum(int[] nums, int target) {int[] num new int[2];for(int i0;i<nums.length-1;i){for(int ji1;j<nums.length;j){if(nums[i]nums[j]target){num[0]i;num[1]j;}}}return num;} }HashMap&#xff0c;记录下标和对应值&…...

Screens for Mac 中文版 远程桌面连接控制工具

Screens Mac 版是Mac os平台上的一款Mac VNC 客户终端,能够自由访问远程计算机设备&#xff0c; Screens Mac 版支持各种强大的远程控制辅助工具&#xff0c;例如剪切板共享、快捷方式自定义、安全连接、多屏幕支持、快速扫描连接等。 Screens 4 for mac支持多种远程桌面协议&…...

解决vmware安装ubuntu虚拟机显示不全以及无法实现windows与虚拟机之间无法相互复制粘贴问题

01、存在问题 02、解决方案 sudo apt-get autoremove open-vm-tools sudo apt-get install open-vm-tools sudo apt-get install open-vm-tools-desktop reboot //重启重启后界面如下&#xff1a; 存在Bug 如果遇到一下问题&#xff0c;请先执行下列命令&#x…...

希腊字母读音表

序号大写小写英文注音国际音标注音中文读音意义1Ααalphaa:lf阿尔法角度&#xff1b;系数2Ββbetabet贝塔磁通系数&#xff1b;角度&#xff1b;系数3Γγgammaˈɡmə伽马电导系数&#xff08;小写&#xff09;4Δδdeltadelt德尔塔变动&#xff1b;密度&#xff1b;屈光度5…...

如何使用CodeceptJS、Playwright和GitHub Actions构建端到端测试流水线

介绍 端到端测试是软件开发的一个重要方面&#xff0c;因为它确保系统的所有组件都能正确运行。CodeceptJS是一个高效且强大的端到端自动化框架&#xff0c;与Playwright 结合使用时&#xff0c;它成为自动化Web、移动甚至桌面 (Electron.js) 应用程序比较好用的工具。 在本文中…...

解析python爬取Ebay数据的方式

前言 Ebay是全球著名的电子商务平台之一&#xff0c;每天都有海量的商品信息涌入其中&#xff0c;在电商行业获取这些数据试试非常有价值的&#xff0c;为了更好地了解市场动态&#xff0c;掌握更多的电商行情。Python爬虫成为了必不可少的工具&#xff0c;本文将通过使用Http…...

设置DevC++支持c++11标准

1.点击编译选项 2. 设置语言标准 3.点击确认 4.测试代码 使用auto成功 测试&#xff01;...

腾讯云服务器CVM详细介绍_优缺点亲自整理

腾讯云服务器CVM提供安全可靠的弹性计算服务&#xff0c;腾讯云明星级云服务器&#xff0c;弹性计算实时扩展或缩减计算资源&#xff0c;支持包年包月、按量计费和竞价实例计费模式&#xff0c;CVM提供多种CPU、内存、硬盘和带宽可以灵活调整的实例规格&#xff0c;提供9个9的数…...

06_es分布式搜索引擎2

一、DSL查询文档 1.DSL查询分类 ①查询所有&#xff1a;match_all ②全文检索&#xff1a;利用分词器对用户输入的内容分词&#xff0c;倒排索引去匹配 match_query multi_match_query ③精确查询&#xff1a;根据精确词条查找数据&#xff0c;查找的是keyword,数值,日期,b…...

【3D图像分割】基于 Pytorch 的 VNet 3D 图像分割3(3D UNet 模型篇)

在本文中&#xff0c;主要是对3D UNet 进行一个学习和梳理。对于3D UNet 网上的资料和GitHub直接获取的代码很多&#xff0c;不需要自己从0开始。那么本文的目的是啥呢&#xff1f; 本文就是想拆解下其中的结构&#xff0c;看看对于一个3D的UNet&#xff0c;和2D的UNet&#x…...

【源码解析】Spring Bean定义常见错误

案例1 隐式扫描不到Bean的定义 RestController public class HelloWorldController {RequestMapping(path "/hiii",method RequestMethod.GET)public String hi() {return "hi hellowrd";}}SpringBootApplication RestController public class Applicati…...

由于找不到vcruntime140.dll无法继续执行代码

在计算机使用过程中&#xff0c;我们可能会遇到一些错误提示&#xff0c;其中之一就是“vcruntime140.dll丢失”。这个错误通常发生在运行某些程序或游戏时&#xff0c;它会导致程序无法正常运行。那么&#xff0c;如何解决vcruntime140.dll丢失的问题呢&#xff1f;本文将介绍…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...

二叉树-144.二叉树的前序遍历-力扣(LeetCode)

一、题目解析 对于递归方法的前序遍历十分简单&#xff0c;但对于一位合格的程序猿而言&#xff0c;需要掌握将递归转化为非递归的能力&#xff0c;毕竟递归调用的时候会调用大量的栈帧&#xff0c;存在栈溢出风险。 二、算法原理 递归调用本质是系统建立栈帧&#xff0c;而非…...