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

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...