洛谷 P3660 USACO17FEB Why Did the Cow Cross the Road III 题解
题意
有一个圆,圆周上按顺时针方向给出 2 n 2n 2n个点。第 i i i个点的颜色是 c o l o r i color_i colori,其中数据保证 1 ≤ c o l o r i ≤ n 1\le color_i\le n 1≤colori≤n,而且每种不同的颜色有且只有两个点。不存在位置重叠的点。在颜色相同的两个点之间连一条边(线段)。
求有多少对边是交叉的?
1 ≤ n ≤ 50000 1\le n \le 50000 1≤n≤50000

思路
转换一下题意,把所谓的“圆圈”拉平成一条直线上的 2 n 2n 2n个点,以相等的两个数的下标作为两端点连一条线段,求线段存在交集且不存在全包含关系的对数。
遇到线段覆盖问题,可以考虑使用树状数组来维护区间内的点数个数。枚举到一条线段,就在树状数组上给两端端点分别加一;计算一条线段 i ( l e − r i ) i(le-ri) i(le−ri)的贡献就是 q u e r y ( r i i − 1 ) − q u e r y ( l e i ) query(ri_i-1)-query(le_i) query(rii−1)−query(lei)
这样算难道不会算重吗?
可以先考虑处理长度更长的线段,如果一条线段 b b b被线段 a a a完全覆盖,必然有 l e n a > l e n b len_a>len_b lena>lenb,此时会先处理 a a a再处理 b b b,就不会多算 b b b的两端节点了。
对于其它的线段,要么与线段 a a a本身相离,当然不会计入贡献,要么一端端点在开区间 ( l e a , r i a ) (le_a,ri_a) (lea,ria)内,计入贡献为 1 1 1。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=1e5+2;
ll n,ans;
struct seg
{ll l,r;
}a[N];
bool cmp(seg x,seg y)
{return x.r-x.l>y.r-y.l;
}
struct BT
{ll T[N];ll lowbit(ll x){return x&(-x);}void add(ll x,ll k){for(int i=x;i<=n*2;i+=lowbit(i))T[i]+=k;}ll query(ll x){ll ret=0;for(int i=x;i>=1;i-=lowbit(i))ret+=T[i];return ret;}
}B;
int main()
{scanf("%lld",&n);for(int i=1;i<=n*2;i++){ll x;scanf("%lld",&x);if(!a[x].l)a[x].l=i;else a[x].r=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){B.add(a[i].l,1);B.add(a[i].r,1);ans+=B.query(a[i].r-1)-B.query(a[i].l);}printf("%lld",ans);return 0;
}
相关文章:
洛谷 P3660 USACO17FEB Why Did the Cow Cross the Road III 题解
题意 有一个圆,圆周上按顺时针方向给出 2 n 2n 2n个点。第 i i i个点的颜色是 c o l o r i color_i colori,其中数据保证 1 ≤ c o l o r i ≤ n 1\le color_i\le n 1≤colori≤n,而且每种不同的颜色有且只有两个点。不存在位置重叠的点…...
【数据结构】(9) 优先级队列(堆)
一、优先级队列 优先级队列不同于队列,队列是先进先出,优先级队列是优先级最高的先出。一般有两种操作:返回最高优先级对象,添加一个新对象。 二、堆 2.1、什么是堆 堆也是一种数据结构,是一棵完全二叉树,…...
如何提升爬虫获取数据的准确性?
提升爬虫获取数据的准确性是确保数据分析和后续应用有效性的关键。以下是一些经过验证的方法和最佳实践,可以帮助提高爬虫数据的准确性: 1. 数据清洗 数据清洗是提升数据准确性的重要步骤,主要包括去除重复数据、处理缺失值和异常值。 去除…...
Obsidian及Zotero常用的插件
Obsidian插件 Minimal Theme Settings(Life,zotero)【必需】 界面样式设置所需插件 Style Settings(Life,zotero)【必需】界面样式设置所需插件 Recent Files(Life,zotero…...
闲鱼IP属地是通过电话号码吗?
在闲鱼这样的二手交易平台上,用户的IP属地信息对于维护交易安全、增强用户间的信任至关重要。然而,关于闲鱼IP属地是如何确定的,不少用户存在疑惑,尤其是它与电话号码之间是否存在关联。本文将深入探讨这一问题,揭示闲…...
C#多线程异步连接MySQL与SQLserver数据库
C#多线程异步连接MySQL与SQLserver数据库 一、前言二、多线程异步连接数据库代码2.1代码块2.2代码说明 参考文档 一、前言 当编写代码连接多台设备上的数据库时,如果采用同步逐个连接的方式,在网络畅通的情况下连接速度尚可,但当其中一台设备…...
51单片机-数码管
目录 1、静态数码管 1.1、数码管是如何显示出字符 1.2、数码管静态显示原理 1.3、74HC573芯片的使用 1.4、静态数码管编程 2、动态数码管 2.1、数码管动态显示原理 2.2、74HC138芯片的使用 2.3、编写动态数码管程序 1、静态数码管 1.1、数码管是如何显示出字符 单片机…...
C#学习之S参数读取(s2p文件)
目录 一、创作灵感 二、S2PFileReader类 1.代码示例 2.代码说明 a.ReadS2PFile 方法: b.DataTable 结构: 三、S2PFileReader类的调用演示 1.使用示例 一、创作灵感 虽然MATLAB处理数据很实用,但是C#常用于程控仪器的控制,…...
Spring Boot “约定大于配置”
什么是“约定大于配置”? “约定大于配置”是一种简化开发的设计理念。简单来说,就是框架默认提供了常见的配置和行为,开发者只需要按照约定来编写代码,避免了繁琐的配置,只在需要时进行定制和调整。这种理念在Spring…...
传输层协议TCP ( 下 )
文章目录 前言序号与确认序号超时重传RTOJacobson算法内核中超时时间的计算 滑动窗口滑动窗口延迟应答流量控制 拥塞控制慢启动拥塞避免快重传快速恢复 保活机制参考资料 前言 TCP(Transmission Control Protocol,传输控制协议)是互联网最重要…...
NLP 八股 DAY1:BERT
BERT全称:Pre-training of deep bidirectional transformers for language understanding,即深度双向Transformer。 模型训练时的两个任务是预测句⼦中被掩盖的词以及判断输⼊的两个句⼦是不是上下句。在预训练 好的BERT模型后⾯根据特定任务加上相应的⽹…...
演示synchronized锁机制用法的简单Demo
演示synchronized锁机制用法的简单Demo。我们以"银行开户"场景为例:每个用户只能创建一个账户(模拟类似原代码中每个用户只能有一个私有空间的限制)。 第1步:创建项目结构 demo-lock ├── src/main/java/com/exampl…...
Datawhale 数学建模导论二 笔记1
第6章 数据处理与拟合模型 本章主要涉及到的知识点有: 数据与大数据Python数据预处理常见的统计分析模型随机过程与随机模拟数据可视化 本章内容涉及到基础的概率论与数理统计理论,如果对这部分内容不熟悉,可以参考相关概率论与数理统计的…...
差分解方程
差分解方程 差分法在数值求解偏微分方程(PDEs)和常微分方程(ODEs)时,可以分为隐式格式和显式格式。以下是两者的主要区别: 显式格式(Explicit Scheme) 时间推进: 显式格…...
EasyExcel 复杂填充
EasyExcel Excel表格中用{}或者{.} 来表示包裹要填充的变量,如果单元格文本中本来就有{、}左右大括号,需要在括号前面使用斜杠转义\{ 、\}。 代码中被填充数据的实体对象的成员变量名或被填充map集合的key需要和Excel中被{}包裹的变量名称一致。 …...
ESP32通过MQTT连接阿里云平台实现消息发布与订阅
文章目录 前言 一、准备工作 二、阿里云平台配置 三、代码实现 总结 前言 本文将介绍如何使用ESP32开发板通过MQTT协议连接阿里云物联网平台,并实现消息的发布与订阅功能。我们将使用Arduino IDE进行开发,并借助PubSubClient库实现MQTT通信。 一、准备…...
NVIDIA Jetson Orin Nano 刷机过程
1. 背景 新到手 NVIDIA Jetson Orin Nano 插上显示屏,显示如下: 这是UEFI Shell,UEFI Shell(统一可扩展固件接口外壳程序)是一种基于UEFI规范的交互式命令行工具,它运行在UEFI固件环境中,为用…...
C#学习之数据转换
目录 一、创作说明 二、数据类型之间的转换 1.数据类型之间的转换表格 2.代码示例 三、进制之间的转换 1.进制之间的转换表格 2.代码示例 四、ASCII 编码和字符之间的转换 1.ASCII 编码和字符之间的转换表格 2.代码示例 五、总结 一、创作说明 C#大多数时候都是和各…...
typecho快速发布文章
typecho_Pytools typecho_Pytools工具由python编写,可以快速批量的在本地发布文章,不需要登陆后台粘贴md文件内容,同时此工具还能查看最新的评论消息。… 开源地址: GitHub Gitee 使用教学:B站 一、主要功能 所有操作不用登陆博…...
深度学习R4周:LSTM-火灾温度预测
🍨 本文为🔗365天深度学习训练营中的学习记录博客🍖 原作者:K同学啊 任务: 数据集中提供了火灾温度(Tem1)、一氧化碳浓度(CO 1)烟雾浓度(Soot 1)…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
java高级——高阶函数、如何定义一个函数式接口类似stream流的filter
java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用(Math::max) 2 函数接口…...
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章 摘要: 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言,受限于 C 语言本身的内存安全和并发安全问题,开发复杂模块极易引入难以…...
内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献
Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译: ### 胃肠道癌症的发病率呈上升趋势,且有年轻化倾向(Bray等人,2018&#x…...
Qt的学习(二)
1. 创建Hello Word 两种方式,实现helloworld: 1.通过图形化的方式,在界面上创建出一个控件,显示helloworld 2.通过纯代码的方式,通过编写代码,在界面上创建控件, 显示hello world; …...
五、jmeter脚本参数化
目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...
