D. Friends and Subsequences 线段树上二分

有个细节,就是query的时候的顺序,不注意到直接T飞,分析知道如果它只在一边的话你直接一边

可以保证复杂度

#include<iostream>
#include<cstring>
#include<algorithm>


const int N = 2e5+10;
using namespace std;
using ll = long long;
int n;
int a[N],b[N];
int tr[2][N<<2];


inline void pushup(int op,int u){
	if(!op)tr[0][u] = max(tr[0][u<<1],tr[0][u<<1|1]);
	if(op)tr[1][u] = min(tr[1][u<<1],tr[1][u<<1|1]);
}


inline void build(int op,int u,int l,int r){
	
	if(l==r){
		if(!op)tr[op][u] = a[l];
		else tr[op][u] = b[l];
		return;
	}
	int mid = (l+r)>>1;
	build(op,u<<1,l,mid),build(op,u<<1|1,mid+1,r);
	pushup(op,u);
}

int hackt;
inline int query(int op,int u,int l,int r,int ql,int qr){
	
	
	if(ql<=l&&r<=qr)return tr[op][u];
	
	
	int mid = (l+r)>>1;
	
	if(qr<=mid)return query(op,u<<1,l,mid,ql,qr);
	else if(ql>mid)return query(op,u<<1|1,mid+1,r,ql,qr);
	else{
		if(!op)return max(query(op,u<<1,l,mid,ql,qr),query(op,u<<1|1,mid+1,r,ql,qr));
		else return min(query(op,u<<1,l,mid,ql,qr),query(op,u<<1|1,mid+1,r,ql,qr));
	}
	
	
}



int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	build(0,1,1,n);
	build(1,1,1,n);

	
	
	ll res = 0;
	for(int i=1;i<=n;i++){
		if(a[i]>b[i])continue;
		int l=i-1,r=n+1;
		while(l+1!=r){
			int mid = (l+r)>>1;
			int tem1 = query(0,1,1,n,i,mid);
			int tem2 = query(1,1,1,n,i,mid);
			if(tem1<tem2)l = mid;
			else r = mid;
		}
 		
		 int ans_l = l+1;
 		
		l = i-1,r = n+1;
		while(l+1!=r){
			int mid = (l+r)>>1;
			int tem1 = query(0,1,1,n,i,mid);
			int tem2 = query(1,1,1,n,i,mid);
			if(tem1<=tem2)l = mid;
			else r = mid;
		}
 		
		 int ans_r = l;
		
 		
		 if(ans_l>ans_r)continue;
		if(query(0,1,1,n,i,ans_l)!=query(1,1,1,n,i,ans_l))continue;
		res = res + ans_r-ans_l+1;
		
	 }
	
	cout<<res<<"\n";
	
	
	
}

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

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

相关文章

MySQL 数据库的日志管理、备份与恢复

一. 数据库备份 1.数据备份的重要性 备份的主要目的是灾难恢复。 在生产环境中&#xff0c;数据的安全性至关重要。 任何数据的丢失都可能产生严重的后果。 造成数据丢失的原因&#xff1a; 程序错误人为,操作错误,运算错误,磁盘故障灾难&#xff08;如火灾、地震&#xff0…

比较AI编程工具Copilot、Tabnine、Codeium和CodeWhisperer

主流的几个AI智能编程代码助手包括Github Copilot、Codeium、Tabnine、Replit Ghostwriter和Amazon CodeWhisperer。 你可能已经尝试过其中的一些&#xff0c;也可能还在不断寻找最适合自己或公司使用的编程助手。但是&#xff0c;这些产品都会使用精选代码示例来实现自我宣传…

Vue挂载全局方法

简介&#xff1a;有时候&#xff0c;频繁调用的函数&#xff0c;我们需要把它挂载在全局的vue原型上&#xff0c;方便调用&#xff0c;具体怎么操作&#xff0c;这里来记录一下。 一、这里以本地存储的方法为例 var localStorage window.localStorage; const db {/** * 更新…

如何在 Mac Pro 上恢复丢失的数据?

无论您多么努力&#xff0c;几乎不可能永远不会无意中删除 Mac 上的文件。当您得知删除后清空了垃圾箱时&#xff0c;您的处境可能看起来很黯淡。不要灰心。我们将教您如何使用本机操作系统功能或数据恢复工具恢复丢失的数据。奇客数据恢复Mac版可帮助恢复已从 Mac Pro 计算机上…

npm救赎之道:探索--save与--save--dev的神秘力量!

目录 1. --save和--save-dev是什么&#xff1f;2. 区别与应用场景--save--save-dev 3. 生产环境与开发环境4. 实际应用示例--save--save-dev 5. 总结 在现代软件开发中&#xff0c;npm&#xff08;Node Package Manager&#xff09;扮演着不可或缺的角色&#xff0c;为开发者提…

Java八股文(JVM)

Java八股文のJVM JVM JVM 什么是Java虚拟机&#xff08;JVM&#xff09;&#xff1f; Java虚拟机是一个运行Java字节码的虚拟机。 它负责将Java程序翻译成机器代码并执行。 JVM的主要组成部分是什么&#xff1f; JVM包括以下组件&#xff1a; ● 类加载器&#xff08;ClassLoa…

HTTP状态 405 - 方法不允许

方法有问题。 用Post发的请求&#xff0c;然后用Put接收的。 大家也可以看看是不是有这种问题 <body><h1>HTTP状态 405 - 方法不允许</h1><hr class"line" /><p><b>类型</b> 状态报告</p><p><b>消息…

如何使用常用的苹果应用商店上架工具提高应用下载量

摘要 移动应用app上架是开发者关注的重要环节&#xff0c;但常常会面临审核不通过等问题。为帮助开发者顺利完成上架工作&#xff0c;各种辅助工具应运而生。本文探讨移动应用app上架原理、常见辅助工具功能及其作用&#xff0c;最终指出合理使用工具的重要性。 引言 移动应…

python(一)网络爬取

在爬取网页信息时&#xff0c;需要注意网页爬虫规范文件robots.txt eg:csdn的爬虫规范文件 csdn.net/robots.txt User-agent: 下面的Disallow规则适用于所有爬虫&#xff08;即所有用户代理&#xff09;。星号*是一个通配符&#xff0c;表示“所有”。 Disallow&…

Groovy结合Java在生产中的落地实战

Groovy简介 Groovy是用于Java虚拟机的一种敏捷的动态语言&#xff0c;是一种成熟的面向对象编程语言&#xff0c;又是一种纯粹的脚本语言。Groovy运行在JVM环境上&#xff0c;在语法上兼具java 语言和脚本语言特点&#xff0c;大大简化了语法。同时又具有闭包和动态语言中的其…

系统分析师-软件开发模型总结

前言 软件工程模型也称软件开发模型。它是指软件开发全部过程、活动和任务的结构框架&#xff0c;通过该模型能清晰、直观地表达软件开发全过程&#xff0c;明确地规定要完成的主要活动和任务&#xff0c;它奠定了软件项目工作的基础 一、瀑布模型&#xff08;Waterfall Model…

Web Components使用(一)

在使用Web Components之前&#xff0c;我们先看看上一篇文章Web Components简介&#xff0c;其中提到了相关的接口、属性和方法。 正是这些接口、属性和方法才实现了Web Components的主要技术&#xff1a;Custom elements&#xff08;自定义元素&#xff09;、Shadow DOM&#…

网络编程--高并发服务器(二)

这里写目录标题 线程池高并发服务器UDP服务器TCP与UDP机制的对比TCP与UDP优缺点比较UDP的C/S模型实现思路模型分析实现思路&#xff08;对照TCP的C/S模型&#xff09; 二级目录 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二…

STM32 PWM通过RC低通滤波转双极性SPWM测试

STM32 PWM通过RC低通滤波转双极性SPWM测试 &#x1f4cd;参考内容《利用是stm32cubemx实现双极性spwm调制 基于stm32f407vet6》&#x1f4fa;相关视频链接&#xff1a;https://www.bilibili.com/video/BV16S4y147hB/?spm_id_from333.788 双极性SPWM调制讲解以及基于stm32的代码…

Machine Learning机器学习之贝叶斯网络(BayesianNetwork)

目录 前言 算法提出背景&#xff1a; 贝叶斯算法特点&#xff1a; 一、贝叶斯定理 二、朴素贝叶斯分类模型 1、朴素贝叶斯分类模型&#xff08;Naive Bayes Classifier&#xff09; 2、原理 2.1 朴素贝叶斯假设 2.2条件独立性假设 2.3后验概率计算 2.4类别预测 2.5小结 3、建模…

【LeetCode热题100】236. 二叉树的最近公共祖先(二叉树)

一.题目要求 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也可…

【计算机网络】http协议的原理与应用,https是如何保证安全传输的

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…

BOM系统:贯穿制造全程的管理利器

在制造行业中&#xff0c;BOM系统的应用已经成为提高生产效率、降低成本和确保产品质量的关键因素。BOM系统作为产品结构和物料清单的管理工具&#xff0c;为制造企业提供了全面的控制和协同能力。 1.产品设计与开发&#xff1a;在产品设计阶段&#xff0c;BOM系统为工程师提供…

uniapp 真机调试(mumu模拟器)

配置mumu模拟器 一、下载Mumu模拟器 https://mumu.163.com/ 二、点击安装&#xff0c;按步骤下一步安卓mumu模拟器 三、打开mumu多开器 右上角adb查看 端口号 四、打开mumu模拟器 五、打开HbuilderX 选择运行&#xff0c;运行到手机模拟器&#xff0c;Android模拟器端口设置…

基于ssm网上服装销售系统论文

摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff1b;对于网上服装销售系统系统当然也不能排除在外&#xff0c;随着网络技术的不断成熟&#xff0c;带动了网上服装销售系统系统&#xff0c;它彻底…