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

二分模板题

题目传送门

主要思路:

  • 暴力会tle n的3次方了
  • 然后 二分可以找中间然后去二分枚举两边
    最后结果 ans+=a小于它的数*c大于它的数 注意要判断是否符合条件 即如果a的小于它的数还大于它就不成立 或者c的数小于它也不成立
  • 结果 要注意转long long ans+=(long long)tp1*tp2; int->longlong
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100009],b[100009],c[100009];
//找到第一个大于该数字的数
int get_max(int *num,int x){int l=1;int r=n; int mid=0;while(l<r){mid=(l+r)/2;if(num[mid]>x) r=mid;else l=mid+1;}return l;
}
// 得到第一个小于它的数
int get_min(int *num,int x)
{int l=1;int r=n; int mid=0;while(l<r){mid=(l+r+1)/2;if(num[mid]<x) l=mid;else r=mid-1;}return l;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];}for(int i=1;i<=n;i++){cin>>c[i];}sort(a+1,a+1+n);sort(c+1,c+1+n);long long ans=0;for(int i=1;i<=n;i++){// cout<<get_max(c,b[i])<<endl;// cout<<get_min(a,b[i])<<endl;// if(b[i]<=a[1]||b[i]>=c[n]) continue;int tp1=n-get_max(c,b[i])+1;int tp2=get_min(a,b[i]);if(c[get_max(c,b[i])]<=b[i]||a[get_min(a,b[i])]>=b[i]) continue;ans+=(long long)tp1*tp2;}cout<<ans<<endl;return 0;
}
// #include <iostream>
// #include <cstdio>
// #include <algorithm>
// using namespace std;// typedef long long LL;
// const int N = 1e5+10;
// int num[3][N];// int main() {
//     int n;
//     scanf("%d", &n);
//     for(int i = 0; i < 3; ++i) 
//         for(int j = 1; j <= n; ++j) 
//             scanf("%d", &num[i][j]);
//     // for(int i = 0; i < 3; ++i)
//         sort(num[0]+1, num[0]+n+1);
//         sort(num[2]+1, num[2]+n+1);
//     LL ans = 0;
//     //枚举B,寻找A满足的个数以及C满足的个数相乘
//     for(int i = 1; i <= n; ++i) {
//         int key = num[1][i];
//         //A中二分查找第一个小于key的数的下标
//         int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
//         //C中二分查找第一个大于key的数的下标
//         int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
//         if(pos1 >= 1 && pos2 <= n) {
//             ans += (LL)pos1*(n-pos2+1);
//         }
//     }
//     cout<<ans<<endl;
//     return 0;
// }

相关文章:

二分模板题

题目传送门 主要思路&#xff1a; 暴力会tle n的3次方了然后 二分可以找中间然后去二分枚举两边 最后结果 ansa小于它的数*c大于它的数 注意要判断是否符合条件 即如果a的小于它的数还大于它就不成立 或者c的数小于它也不成立结果 要注意转long long ans(long long)tp1*tp2; …...

一篇文章掌握Git的基本原理与使用

目录 一、创建仓库 1.1 git init 1.2 git clone 二、工作区域与文件状态 三、添加和提交文件 3.1 git status 3.2 git add git rm --cached 3.3 git commit git log 四、版本回退 soft hard mixed 总结 五、查看差异 工作区与暂存区 工作区与本地仓库 暂存区…...

「Mac畅玩鸿蒙与硬件43」UI互动应用篇20 - 闪烁按钮效果

本篇将带你实现一个带有闪烁动画的按钮交互效果。通过动态改变按钮颜色&#xff0c;用户可以在视觉上感受到按钮的闪烁效果&#xff0c;提升界面互动体验。 关键词 UI互动应用闪烁动画动态按钮状态管理用户交互 一、功能说明 闪烁按钮效果应用实现了一个动态交互功能&#xf…...

朗新科技集团如何用云消息队列 RocketMQ 版“快、准、狠”破解业务难题?

作者&#xff1a;邹星宇、刘尧 朗新科技集团&#xff1a;让数字化的世界更美好 朗新科技集团股份有限公司是领先的能源科技企业&#xff0c;长期深耕电力能源领域&#xff0c;通过新一代数字化、人工智能、物联网、电力电子技术等新质生产力&#xff0c;服务城市、产业、生活中…...

【Ubuntu】Ubuntu的Desktop(学习/用户使用)和Bit版本(工作)

这篇文章似乎没什么必要写&#xff0c;但想了想还是决定记录一下&#xff0c;也许对新手入坑Ubuntu会有帮助&#xff0c; 事实上也很简单&#xff0c;一个是桌面版本&#xff0c;另一个是字符界面版本。 桌面版&#xff1a;拥有图形桌面 字符界面&#xff0c;易上手&#xff…...

cmake CMAKE_CURRENT_SOURCE_DIR和CMAKE_CURRENT_LIST_DIR的区别

在 CMake 中&#xff0c;CMAKE_CURRENT_LIST_DIR 和 CMAKE_CURRENT_SOURCE_DIR 都是指代当前 CMake 文件所在的路径&#xff0c;但它们的含义和用途有所不同&#xff1a; CMAKE_CURRENT_LIST_DIR&#xff1a; 表示 当前处理的 CMake 文件&#xff08;例如 CMakeLists.txt&#…...

学会用VSCode debug

本文主要介绍了 VS Code 的调试功能&#xff0c;包括其强大的内置调试器&#xff0c;支持多种语言&#xff0c;如 JavaScript、TypeScript 等。通过简单项目示例展示调试过程&#xff0c;还介绍了运行面板和菜单、启动配置、调试操作、断点、记录点等功能&#xff0c;以及三种调…...

C语言专题之结构体的使用

结构体&#xff08;struct&#xff09;是一种用户自定义的数据类型&#xff0c;它允许将不同类型的数据组合在一起&#xff0c;形成一个新的数据类型。结构体在编程中非常常见&#xff0c;尤其是在需要处理复杂数据结构的情况下。以下是结构体的基本使用方法&#xff1a; 一、结…...

python中的高阶函数

1、什么是高阶函数&#xff1f; 高阶函数是指将函数作为参数传入。就是高阶函数 2、高阶函数有哪些&#xff1f; map 映射函数 >>> print(list(map(lambda x:x*x,range(1,11)))) [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] >>> print(list(map(lambda x:st…...

学习笔记063——通过使用 aspose-words 将 Word 转 PDF 时,遇到的字体改变以及乱码问题

文章目录 1、问题描述&#xff1a;2、解决方法&#xff1a; 1、问题描述&#xff1a; Java项目中&#xff0c;有个需要将word转pdf的需求。本人通过使用aspose-words来转换的。在Windows中&#xff0c;转换是完全正常的。但是当部署到服务器时&#xff0c;会出现转换生成的pdf…...

SpringBoot整合Mockito进行单元测试超全详细教程 JUnit断言 Mockito 单元测试

Mock概念 Mock叫做模拟对象&#xff0c;即用来模拟未被实现的对象可以预先定义这个对象在特定调用时的行为&#xff08;例如返回值或抛出异常&#xff09;&#xff0c;从而模拟不同的系统状态。 导入Mock依赖 pom文件中引入springboot测试依赖&#xff0c;spring-boot-start…...

【AI知识】过拟合、欠拟合和正则

一句话总结&#xff1a; 过拟合和欠拟合是机器学习中的两个相对的概念&#xff0c;正则化是用于解决过拟合的方法。 1. 欠拟合&#xff1a; 指模型在训练数据上表现不佳&#xff0c;不能充分捕捉数据的潜在规律&#xff0c;导致在训练集和测试集上的误差都很高。欠拟合意味着模…...

MacOS编译webRTC源码小tip

简单记录一下&#xff0c;本人在编译webRTC时&#xff0c;碰到了一下比较烦人的问题&#xff0c;在MacOS终端下&#xff0c;搭建科学上网之后&#xff0c;chromium的depot_tools仓库成功拉下来了&#xff0c;紧接着&#xff0c;使用fetch以及gclient sync始终都返回curl相关的网…...

Linux基础命令(三):文件压缩及解压缩命令

文件压缩及解压缩命令 tar — 打包和压缩 tar 是一个用于打包文件的工具&#xff0c;常常用来将多个文件或目录打包成一个单独的文件。它本身不进行压缩&#xff0c;但可以与压缩工具&#xff08;如 gzip 或 bzip2&#xff09;一起使用。 用法&#xff1a; 打包文件&#xff0…...

目标跟踪算法:ByteTrack、卡尔曼滤波、匈牙利算法、高置信度检测目标、低置信度检测目标

目录 1 ByteTrack特点 2 ByteTrack和SORT区别----个人通俗理解 3 ByteTrack算法原理 4 ByteTrack整体流程图 上一篇博客我复习了下SORT跟踪算法&#xff0c;这一篇博客我再复习下ByteTrack跟踪算法&#xff0c;ByteTrack里面也是用了卡尔曼滤波和匈牙利算法&#x…...

[定昌linux系统]如何安装jdk8

1:下载jdk8 的 arm64 的版本&#xff0c;由于官方下载需要gmail&#xff0c;我的gmail 密码忘了&#xff0c;所以从csdn上下载了一份&#xff0c;地址&#xff1a; https://download.csdn.net/download/qq_27742163/88533548?utm_mediumdistribute.pc_relevant_download.none…...

【Cadence32】PCB多层板电源、地平面层创建心得➕CM约束管理器Analyze分析显示设置➕“DP”报错DRC

【转载】Cadence Design Entry HDL 使用教程 【Cadence01】Cadence PCB Edit相对延迟与绝对延迟的显示问题 【Cadence02】Allegro引脚焊盘Pin设置为透明 【Cadence03】cadence不小心删掉钢网层怎么办&#xff1f; 【Cadence04】一般情况下Allegro PCB设计时的约束规则设置&a…...

基于SpringBoot+Vue的新闻管理系统

系统展示 用户前台界面 管理员后台界面 系统背景 随着互联网技术的飞速发展&#xff0c;信息传播速度不断加快&#xff0c;新闻媒体行业面临着巨大的机遇与挑战。传统的新闻媒体正在逐渐向数字化转型&#xff0c;而新闻管理系统作为数字化新闻媒体的核心组成部分&#xff0c;其…...

图的割点、割边(Tarjan算法)

深度优先搜索的利用。 在一个无向连通图中&#xff0c;如果删掉某个顶点后&#xff0c;图不再连通&#xff08;即任意两点之间不能互相到达&#xff09;&#xff0c;我们称这样的顶点为割点。 在一个无向连通图中&#xff0c;如果删掉某条边后&#xff0c;图不在连通&#xff0…...

算法学习(十四)—— 二叉树的深度搜索(DFS)

目录 关于dfs 部分OJ题详解 2331. 计算布尔二叉树的值 129. 求根节点到叶节点数字之和 814. 二叉树剪枝 98. 验证二叉搜索树 230. 二叉搜索树中第K小的元素 257. 二叉树的所有路径 关于dfs 算法学习&#xff08;十二&#xff09;—— 递归&#xff0c;搜索&#xff0c…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...