当前位置: 首页 > 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…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#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可以提供外设…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

从零手写Java版本的LSM Tree (一):LSM Tree 概述

&#x1f525; 推荐一个高质量的Java LSM Tree开源项目&#xff01; https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree&#xff0c;专为高并发写入场景设计。 核心亮点&#xff1a; ⚡ 极致性能&#xff1a;写入速度超…...

CppCon 2015 学习:REFLECTION TECHNIQUES IN C++

关于 Reflection&#xff08;反射&#xff09; 这个概念&#xff0c;总结一下&#xff1a; Reflection&#xff08;反射&#xff09;是什么&#xff1f; 反射是对类型的自我检查能力&#xff08;Introspection&#xff09; 可以查看类的成员变量、成员函数等信息。反射允许枚…...