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

上海网站建设专业公司/热门职业培训班

上海网站建设专业公司,热门职业培训班,微餐饮网站建设官网,写作网站哪个最好https://atcoder.jp/contests/arc165/tasks/arc165_f 首先可以建图&#xff0c;然后变成求字典序最小的的拓扑排序 然后发现这样复杂度会炸&#xff0c;观察连边的条件是什么&#xff1a; l i < l j l_i<l_j li​<lj​ r i < r j r_i<r_j ri​<rj​ 这是个…

https://atcoder.jp/contests/arc165/tasks/arc165_f

首先可以建图,然后变成求字典序最小的的拓扑排序

然后发现这样复杂度会炸,观察连边的条件是什么:

  • l i < l j l_i<l_j li<lj
  • r i < r j r_i<r_j ri<rj

这是个二维偏序问题,我们考虑用分治来解决

我们按 l l l 排序,本区间内再按 r r r 排序:

在这里插入图片描述

复杂度 O ( n log ⁡ 2 n ) O(n\log^2n) O(nlog2n)

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else#define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 5000010
//#define M
//#define mo
struct node {int l, r, id, op; 
}a[N];
int n, m, i, j, k, T;
struct cmp {bool operator () (int x, int y) const {if(x<=n && y>n) return 1; if(y<=n && x>n) return 0; if(x<=n && y<=n) return x>y; if(x>n && y>n) return x>y; }
};
priority_queue<int, vector<int>, cmp >q; 
int c[N], b[N], tot; 
vector<int>G[N]; void cun(int x, int y) {
//	debug("%d -> %d\n", x, y); G[x].pb(y); ++c[y]; 
}void solve(int l, int r) {int i; if(l==r) return ; int mid=(l+r)>>1; solve(l, mid); solve(mid+1, r); for(i=l; i<=mid; ++i) a[i].op=0; for(i=mid+1; i<=r; ++i) a[i].op=1; sort(a+l, a+r+1, [&] (node x, node y) { return x.r<y.r; }); for(i=l; i<=r; ++i) b[i]=++tot; for(i=l; i<=r-1; ++i) cun(b[i], b[i]+1); for(i=l; i<=r; ++i) if(a[i].op==0) cun(a[i].id, b[i]); else cun(b[i], a[i].id); 
}signed main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif
//	T=read();
//	while(T--) {
//
//	}n=read(); tot=n; for(i=1; i<=n; ++i) a[i].id=i; for(i=1; i<=2*n; ++i) {k=read(); if(!a[k].l) a[k].l=i; else a[k].r=i; }sort(a+1, a+n+1, [] (node x, node y) { return x.l<y.l; }); solve(1, n); for(i=1; i<=tot; ++i) if(!c[i]) q.push(i); while(!q.empty()) {auto u=q.top(); q.pop(); 
//		debug("# %d\n",  u); if(u<=n) printf("%d %d ", u, u); for(auto v : G[u]) if(--c[v]==0) q.push(v); }return 0;
}

相关文章:

偏序关系用分治优化建图:ARC165F

https://atcoder.jp/contests/arc165/tasks/arc165_f 首先可以建图&#xff0c;然后变成求字典序最小的的拓扑排序 然后发现这样复杂度会炸&#xff0c;观察连边的条件是什么&#xff1a; l i < l j l_i<l_j li​<lj​ r i < r j r_i<r_j ri​<rj​ 这是个…...

StripedFly恶意软件:悄无声息运行5年,感染百万设备

导语&#xff1a;最近&#xff0c;俄罗斯网络安全公司Kaspersky发布的一项调查显示&#xff0c;一种名为StripedFly的高级恶意软件伪装成加密货币挖矿程序&#xff0c;悄无声息地在全球范围内运行了超过5年&#xff0c;感染了100万台设备。这是一种复杂的模块化框架&#xff0c…...

Flink SQL DataGen Connector 示例

Flink SQL DataGen Connector 示例 1、概述 使用 Flink SQL DataGen Connector&#xff0c;可以快速地生成符合规则的测试数据&#xff0c;可以在不依赖真实数据的情况下进行开发和测试。 2、使用示例 创建一个名为 “users” 的表&#xff0c;包含 6 个字段&#xff1a;id…...

【监控指标】监控系统-prometheus、grafana。容器化部署。go语言 gin框架、gRPC框架的集成

文章目录 一、监控有哪些指标二、prometheus、grafana架构Prometheus 组件Grafana 组件架构优点 三、安装prometheus和node-exporter1. docker pull镜像2. 启动node-exporter3. 启动prometheus 四、promql基本语法五、grafana的安装和使用1. 新建空文件夹grafana-storage&#…...

时序分解 | Matlab实现PSO-VMD粒子群算法优化变分模态分解时间序列信号分解

时序分解 | Matlab实现PSO-VMD粒子群算法优化变分模态分解时间序列信号分解 目录 时序分解 | Matlab实现PSO-VMD粒子群算法优化变分模态分解时间序列信号分解效果一览基本介绍程序设计参考资料 效果一览 基本介绍 PSO-VMD粒子群算法PSO优化VMD变分模态分解 可直接运行 分解效果…...

leetcode 684. 冗余连接

树可以看成是一个连通且 无环 的 无向 图。 给定往一棵 n 个节点 (节点值 1&#xff5e;n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间&#xff0c;且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges &#xff0c;edges[i] …...

yolov8模型训练、目标跟踪

一、准备条件 1.下载yolov8 https://github.com/ultralytics/ultralytics2.安装python https://www.python.org/ftp/python/3.8.0/python-3.8.0-amd64.exe3.安装依赖 进入ultralytics-main&#xff0c;执行&#xff1a; pip install -r requirements.txt pip install -U ul…...

Flink SQL Regular Join 、Interval Join、Temporal Join、Lookup Join 详解

Flink ⽀持⾮常多的数据 Join ⽅式&#xff0c;主要包括以下三种&#xff1a; 动态表&#xff08;流&#xff09;与动态表&#xff08;流&#xff09;的 Join动态表&#xff08;流&#xff09;与外部维表&#xff08;⽐如 Redis&#xff09;的 Join动态表字段的列转⾏&#xf…...

如何在搜索引擎中应用AI大语言模型,提高企业生产力?

人工智能尤其是大型语言模型的应用&#xff0c;重塑了我们与信息交互的方式&#xff0c;也为企业带来了重大的变革。将基于大模型的检索增强生成&#xff08;RAG&#xff09;集成到业务实践中&#xff0c;不仅是一种趋势&#xff0c;更是一种必要。它有助于实现数据驱动型决策&…...

实验七 组合器模式的应用

实验目的 1)掌握组合器模式&#xff08;composite&#xff09;的特点 2 分析具体问题&#xff0c;使用组合器模式进行设计。 实验内容和要求 在例3.3的设计中&#xff0c;添加一个空军大队( Wing)类&#xff0c;该类与Squadron、Group类是平行的&#xff0c;因此应该继承了AirU…...

Springboot实现人脸识别与WebSocket长连接的实现

0.什么是WebSocket,由于普通的请求是间断式发送的,如果要同一时间发生大量的请求,必然导致响应速度慢(因为根据tcp协议要经过三层握手,如果不持续发送,就会导致n多次握手,关闭连接,打开连接) 1.业务需求: 由于我需要使用java来处理视频的问题,视频其实就是图片,相当于每张图片…...

智能安全帽功能-EIS智能防抖摄像头4G定位视频语音气体检测

智能安全帽是一种集成多种智能功能的产品&#xff0c;例如实时定位、语音对讲、健康监测和AI智能预警等。这些丰富的功能能够更好地帮助工人开展工作&#xff0c;并提升安全保障水平。智能安全帽在各个行业中的应用越来越广泛。尤其在工程建设领域&#xff0c;项目管理和工作安…...

TEMU跨境平台珠宝首饰RSL报告如何办理?

首饰或者产品TEMU拼多多跨境平台要求的RSL报告如何办理&#xff1f; 珠宝首饰上架前必须进行RSL Report&#xff08;欧盟禁限用化学物质检测报告&#xff09; 随着人们对珠宝首饰的要求越来越高&#xff0c;为了确保珠宝首饰的安全性&#xff0c;欧盟REACH法规规定&#xff0c…...

51单片机的篮球计分器液晶LCD1602显示( proteus仿真+程序+原理图+PCB+设计报告+讲解视频)

51单片机的篮球计分器液晶LCD1602显示 &#x1f4d1;1.主要功能&#xff1a;&#x1f4d1;讲解视频&#xff1a;&#x1f4d1;2.仿真&#x1f4d1;3. 程序代码&#x1f4d1;4. 原理图&#x1f4d1;5. PCB图&#x1f4d1;6. 设计报告&#x1f4d1;7. 设计资料内容清单&&…...

【NI-DAQmx入门】NI-DAQmx之Python

NI-DAQmx Python GitHub资源&#xff1a; NI-DAQmx Python 文档说明&#xff1a;NI-DAQmx Python Documentation — NI-DAQmx Python API 0.9 documentation nidaqmx支持 CPython 3.7和 PyPy3&#xff0c;需要注意的是多支持USB DAQ和PCI DAQ&#xff0c;cDAQ需要指定…...

YoloV8目标检测与实例分割——目标检测onnx模型推理

一、模型转换 1.onnxruntime ONNX Runtime&#xff08;ONNX Runtime或ORT&#xff09;是一个开源的高性能推理引擎&#xff0c;用于部署和运行机器学习模型。它的设计目标是优化执行使用Open Neural Network Exchange&#xff08;ONNX&#xff09;格式定义的模型&#xff0c;…...

pcigo图床插件的简单开发

1.前言&#xff1a; 如果想写一个图床并且投入使用&#xff0c;那么&#xff0c;接入picgo一定是一个不错的选择。picgo有着windows&#xff0c;mac&#xff0c;linux等多个客户端版本。实用且方便。 2. 开发的准备&#xff1a; 2.0. 需要安装一个node node这里我就不详细说…...

Find My手机保护壳|苹果Find My与手机保护壳结合,智能防丢,全球定位

随着科技水平的快速发展&#xff0c;科技美容这一行业做为新型产业新生而出。时尚IT品牌随着市场的多元化发展。针对手机品牌和功能的增加而呈多样化&#xff0c;将手机保护壳按质地分有PC壳&#xff0c;皮革 &#xff0c;硅胶&#xff0c;布料&#xff0c;硬塑&#xff0c;皮套…...

encode和decode的区别

字节序列和字符串是Python中两种不同的数据类型&#xff0c;它们的主要区别在于表示和处理方式&#xff01; 字节序列&#xff08;Bytes&#xff09;&#xff1a; 字节序列是一种二进制数据类型&#xff0c;它由一系列字节组成。字节是计算机存储信息的基本单位&#xff0c;每…...

建设项目管理中的 5 大预算挑战

为建设项目管理制定可靠、准确的预算是一项艰巨的任务&#xff0c;对于中小型建筑企业来说尤其如此。预算必须精确&#xff0c;同时还要考虑到每项工作的独特性和复杂性。 一项建筑行业相关调查统计了参与施工预算流程的人员所面临的最大挑战&#xff0c;分别是时间、预算、不…...

vue2 集成 - 超图-SuperMap iClient3D for WebGL

1:下载SuperMap iClient3D for WebGL SuperMap iClient3D for WebGL产品包 打开资源目录如下 2:格式化项目中所用的依赖包 开发指南 从超图官网下载SuperMap iClient3D 11i (2023) SP1 for WebGL_CN.zip解压后,将Build目录下的SuperMap3D复制到项目中 \public\static…...

FPGA设计过程中有关数据之间的并串转化

1.原理 并串转化是指的是完成串行传输和并行传输两种传输方式之间的转换的技术&#xff0c;通过移位寄存器可以实现串并转换。 串转并&#xff0c;将数据移位保存在寄存器中&#xff0c;再将寄存器的数值同时输出&#xff1b; 并转串&#xff0c;将数据先进行移位&#xff0…...

hologres基础知识一文全

1 功能特性 1.1多场景查询分析 Hologres支持行存、列存、行列共存等多种存储模式和索引类型,同时满足简单查询、复杂查询、即席查询等多样化的分析查询需求。Hologres使用大规模并行处理架构,分布式处理SQL,提高资源利用率,实现海量数据极速分析。 亚秒级交互式分析 Holo…...

阿里云oss迁移到AWS S3

这里写自定义目录标题 0.项目背景1.rclone 方式2.rsync方式3.注意 0.项目背景 公司迁移要求&#xff1a;从阿里云oss到亚马逊s3&#xff0c;数据量大概500G-2T左右。 开启阿里云oss 加速模式&#xff0c;这样能够跨机房和区域加速。 主要采用以下两种方式同步数据&#xff0c;…...

RabbitMQ(高级特性):限流

消费端限流 在rabbitmq中&#xff0c;使用消费端限流必须开启手动签收信息 过MQ可以对请求进行“削峰填谷”&#xff0c;即通过消费端限流的方式限制消息的拉取速度&#xff0c;达到保护消费端的目的。 生产者批量发送消息&#xff1a; Test public void testSendBatch() {…...

LeetCode--570. 至少有5名直接下属的经理

文章目录 1 题目描述2 测试用例3 解题思路3.1 解法 1 1 题目描述 表: Employee ---------------------- | Column Name | Type | ---------------------- | id | int | | name | varchar | | department | varchar | | managerId | in…...

Ubuntu20.04下安装Redis环境

apt安装Redis环境 更新apt-get安装镜像源 安装Redis sudo apt-get install -y redis-server设置密码 # 编辑Redis的配置文件redis.conf&#xff0c;如果不知道配置文件的位置可以执行whereis redis.conf查看 sudo vim /etc/redis/redis.conf取消文件中的requirepass注释&am…...

什么是用户体验测试? 为什么很重要?

在当今数字化时代&#xff0c;用户体验(User Experience&#xff0c;简称UX)已经成为产品成功的关键因素之一。无论是应用程序、网站、硬件设备还是软件&#xff0c;提供出色的用户体验不仅能够吸引更多用户&#xff0c;还能够增加用户满意度&#xff0c;提高品牌忠诚度&#x…...

Android 图片翻面动画

一、需求描述 项目需要实现塔罗牌的翻面效果&#xff0c;需要点击图片后&#xff0c;图片实现翻面&#xff0c;并且翻面过程中&#xff0c;替换成图片资源&#xff0c;类似于扑克牌翻面。 二、实现思路 图片实现翻面效果&#xff0c;并且在动画执行到一半&#xff08;刚好到图…...

如何恢复已删除的PDF文件?4个常用方法分享(含操作步骤)!

“不小心删除了一些比较重要的PDF文件&#xff0c;大家能不能帮帮忙呀&#xff1f;有没有方法可以恢复已经删除的PDF文件呢&#xff1f;” PDF文件在我们的日常工作和生活中扮演着重要的角色&#xff0c;我们可能经常都需要使用到它。但不可避免的是&#xff0c;我们在使用电脑…...