CF687D Dividing Kingdom II 题解
Description
给定一个 n n n 个点、 m m m 条边的图,有 q q q 次询问,每次询问一个 [ l , r ] [l,r] [l,r] 的区间,求将 n n n 个点分为两个部分后,编号在 [ l , r ] [l,r] [l,r] 内的边中,两端点属于同一部分的边权最大值最小是多少。
Solution
转换一下题意,删去一些边使得剩下的图是一个二分图,使得删去的边权最大值最小。
上来看到最大值最小,立马想到二分答案,每次二分一个边权 m i d mid mid,将所有边权大于 m i d mid mid 的加入图中,用扩展域并查集判断是否是二分图。
时间复杂度 O ( q log m ( n + m α ( n ) ) ) O(q\log m(n+m\alpha(n))) O(qlogm(n+mα(n)))。
但是你发现 O ( log m ) O(\log m) O(logm) 是没必要的,先将边按边权从大到小排序,若编号属于 [ l , r ] [l,r] [l,r] 就加入图中,如果加完这条边变奇图了那么这条边的边权就是答案。
时间复杂度 O ( q ( n + m α ( n ) ) ) O(q(n+m\alpha(n))) O(q(n+mα(n))),由于 CF
的神仙机子以及 6 6 6 秒的实现可以暴力通过。
考虑如何优化,发现每一次加入边后的图实际上只有 O ( n ) O(n) O(n) 条边会对下次加边造成影响,即一些树边(可能是森林)和可能有的一条边权最大的非树边(当前答案),它们可以代表当前的图,同时一些边在多组询问中都被并入一次,而将询问上到线段树上就可以避免。
所以我们开一棵线段树,节点 [ l , r ] [l,r] [l,r] 表示将编号 [ l , r ] [l,r] [l,r] 的边并完后能代表这个图的 O ( n ) O(n) O(n) 条边,同时按边权从大到小排序,合并时先归并排序,将左右儿子的代表边集和在一起,然后求出新图的代表边集,建树复杂度为 O ( m log m α ( n ) ) O(m\log m\alpha(n)) O(mlogmα(n))。
查询时将 [ l , r ] [l,r] [l,r] 的代表边集暴力求答案,复杂度 O ( q n α ( n ) log m ) O(qn\alpha(n)\log m) O(qnα(n)logm)。
还可以继续,将询问离线离散化,树上节点 [ l , r ] [l,r] [l,r] 表示 [ b l , b r + 1 ) [b_l,b_{r+1}) [bl,br+1) 区间的代表边集,其中 b b b 是离散数组。
记得离散询问 [ l , r ] [l,r] [l,r] 时,离散 l l l 和 r + 1 r+1 r+1,查询时取出 [ c l , c r + 1 − 1 ] [c_l,c_{r+1}-1] [cl,cr+1−1] 的代表集暴力即可,其中 c i c_i ci 表示 i i i 离散后的编号,若询问中没有 1 1 1 和 m m m,记得加进离散。
时间复杂度 O ( m log q α ( n ) + q n α ( n ) log q ) O(m\log q\alpha(n)+qn\alpha(n)\log q) O(mlogqα(n)+qnα(n)logq)。
Code
#include<bits/stdc++.h>
using namespace std;
#define ls x<<1
#define rs x<<1|1
struct edge{int x,y,z;
}e[1000010];
bool cmp(edge x,edge y){return x.z>y.z;
}
#define ve vector<edge>
int n,m,q,tot;
int b[6060],siz[2020],fa[2020];
ve tr[4000040];
struct que{int l,r;
}qu[3030];
int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}
bool uni(int x,int y){int fx=find(x),fy=find(y);if(fx==fy) return 0;if(siz[fx]>siz[fy]) swap(fx,fy);siz[fy]+=siz[fx];fa[fx]=fy;return 1;
}
void reset(int x){fa[x]=x,fa[x+n]=x+n;siz[x]=1,siz[x+n]=1;
}
pair<ve,int> solve(ve tmp){ve ans;for(auto x:tmp){reset(x.x),reset(x.y);}for(auto i:tmp){int x=find(i.x),y=find(i.y);if(x!=y){if(uni(i.x,i.y+n)&&uni(i.y,i.x+n)){ans.push_back(i);}}else{ans.push_back(i);return {ans,i.z};break;}}return {ans,-1};
}
ve merge(ve l,ve r){ve tmp;int fl1=0,fl2=0;while(fl1<l.size()&&fl2<r.size()){if(cmp(l[fl1],r[fl2])){tmp.push_back(l[fl1++]);}else{tmp.push_back(r[fl2++]);}}while(fl1<l.size()) tmp.push_back(l[fl1++]);while(fl2<r.size()) tmp.push_back(r[fl2++]);auto ans=solve(tmp);return ans.first;
}
void build(int x,int l,int r){if(l==r){ve tmp;for(int i=b[l];i<b[l+1];i++){tmp.push_back(e[i]);}sort(tmp.begin(),tmp.end(),cmp);auto ans=solve(tmp);tr[x]=ans.first;return ;}int mid=l+r>>1;build(ls,l,mid),build(rs,mid+1,r);tr[x]=merge(tr[ls],tr[rs]);
}
ve query(int x,int l,int r,int L,int R){if(l>=L&&r<=R){return tr[x];}int mid=l+r>>1;if(R<=mid) return query(ls,l,mid,L,R);if(L>=mid+1) return query(rs,mid+1,r,L,R);return merge(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
int main(){ios::sync_with_stdio(0);cin.tie(nullptr);cin>>n>>m>>q;for(int i=1;i<=m;i++){cin>>e[i].x>>e[i].y>>e[i].z;}for(int i=1;i<=q;i++){cin>>b[++tot]>>b[++tot];b[tot]++;qu[i]={b[tot-1],b[tot]};}b[++tot]=1;sort(b+1,b+1+tot);tot=unique(b+1,b+1+tot)-b-1;b[tot+1]=m+1; //注意细节build(1,1,tot);for(int i=1;i<=q;i++){int l=lower_bound(b+1,b+1+tot,qu[i].l)-b;int r=lower_bound(b+1,b+1+tot,qu[i].r)-b-1;ve tmp=query(1,1,tot,l,r);int ans=solve(tmp).second;cout<<ans<<'\n';}return 0;
}
相关文章:
CF687D Dividing Kingdom II 题解
Description 给定一个 n n n 个点、 m m m 条边的图,有 q q q 次询问,每次询问一个 [ l , r ] [l,r] [l,r] 的区间,求将 n n n 个点分为两个部分后,编号在 [ l , r ] [l,r] [l,r] 内的边中,两端点属于同一部分的…...

高空抛物AI检测算法:精准防控,技术革新守护城市安全
近年来,随着城市化进程的加速,高楼大厦如雨后春笋般涌现,但随之而来的高空抛物问题却成为城市管理的一大难题。高空抛物不仅严重威胁行人的安全,还可能引发法律纠纷和社会问题。为了有效预防和减少高空抛物事件的发生,…...

html+css+js实现Collapse 折叠面板
实现效果: HTML部分 <div class"collapse"><ul><li><div class"header"><h4>一致性 Consistency</h4><span class"iconfont icon-jiantou"></span></div><div class"…...
RM服务器研究(一)
客户端默认端口是10100: MultiPort.dll BOOL sub_10001070() { UINT v0; // esi BOOL result; // eax CHAR KeyName; // [espCh] [ebp-10Ch] DWORD flOldProtect; // [esp10h] [ebp-108h] CHAR Buffer; // [esp14h] [ebp-104h] char v5; // [esp15h] [e…...

云岚到家xxl job 配置
调度中心: 负责管理调度信息,按照调度配置发出调度请求,自身不承担业务代码; 主要职责为执行器管理、任务管理、监控运维、日志管理等 任务执行器: 负责接收调度请求并执行任务逻辑; 主要职责是执行任…...
国内动态短效sk5
HTTP爬虫代理,软件测试, 动态转发IP方案,全高匿名,私密IP,固定网关将您每次请求的HTTP重定向到不同的后端IP,支持API;指路小熊IP https://www.xiaoxiongip.com?fromqkJWgD可测...

【路径规划】路径平滑算法,A星算法拐点的圆弧化处理
摘要 A算法广泛应用于路径规划中,但其生成的路径通常在拐点处呈现不平滑的折线。为了提升路径的平滑性,本文提出了一种基于圆弧的平滑处理方法,用于对A算法产生的路径拐点进行优化。通过在MATLAB中进行仿真验证,该方法能够有效减…...

【寻找one piece的算法之路】——双指针算法!他与她是否会相遇呢?
💐个人主页:初晴~ 📚相关专栏:寻找one piece的刷题之路 什么是双指针算法 双指针算法是一种常用的编程技巧,尤其在处理数组和字符串问题时非常有效。这种方法的核心思想是使用两个指针来遍历数据结构,这两…...

UFS 3.1架构简介
整个UFS协议栈可以分为三层:应用层(UFS Application Layer(UAP)),传输层(UFS Transport Layer(UTP)),链路层(UIC InterConnect Layer(UIC))。应用层发出SCSI命令(UFS没有自己的命令使用的是简化的SCSI命令),在传输层将SCSI分装为UPIU,再经过链路层将命令发送给Devices。下…...

注册安全分析报告:科研诚信查询平台无验证方式导致安全隐患
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 1. 暴力破解密码,造成用户信息泄露 2. 短信盗刷的安全问题,影响业务及导致用户投诉 3. 带来经济损失,尤其是后付费客户,风险巨大,造…...
04.useTitle
在 React 应用中,动态更新页面标题是提升用户体验的一个重要方面。它可以让用户更清楚地知道当前页面的内容或状态,特别是在单页应用(SPA)中。useTitle 钩子提供了一种简单而有效的方式来管理文档标题。以下是如何实现和使用这个自定义钩子: const useTitle = title =>…...
ROS2中的srv、action、发布订阅三种方式
ROS2中的srv、action、发布订阅三种方式 以下是ROS2中srv、action、发布订阅三种方式的差异和使用场景的表格形式呈现: 特性/方式srv(服务)action(动作)发布订阅(Publish-Subscribe)通信模式请…...

HarmonyOS/OpenHarmony 自定义弹窗页面级层级控制解决方案
关键词:CuntomDialog自定义弹窗、SubWindow子窗口、页面级、弹窗层级控制、鸿蒙、弹窗展示层级异常 问题存在API版本:API10 - API12(该问题已反馈,期望后续官方能增加页面级控制能力) 在正常的鸿蒙app开发过程中&…...

C/C++进阶(一)--内存管理
更多精彩内容..... 🎉❤️播主の主页✨😘 Stark、-CSDN博客 本文所在专栏: 学习专栏C语言_Stark、的博客-CSDN博客 其它专栏: 数据结构与算法_Stark、的博客-CSDN博客 项目实战C系列_Stark、的博客-CSDN博客 座右铭&a…...

docker-compose 快速部署clickhouse集群
在本教程中,我们将学习如何使用 Docker Compose 部署一个带有三节点的 ClickHouse 集群,并使用 ZooKeeper 作为分布式协调服务。 前提条件 注意事项: 镜像版本号注意保持一致 [zookeeper:3.7, clickhouse/clickhouse-server:22.5.4]config…...

闯关训练三:Git 基础知识
任务1: 破冰活动:自我介绍 点击Fork目标项目,创建一个新的Fork 获取仓库链接 在连接好开发机的vscode终端中逐行执行以下代码: git clone https://github.com/KelvinIII/Tutorial.git # 修改为自己frok的仓库 cd Tutorial/ git branch -a g…...

Java--IO基本流
IO流 概述 生活中,你肯定经历过这样的场景。当你编辑一个文本文件,忘记了ctrls ,可能文件就白白编辑了。当你电脑上插入一个U盘,可以把一个视频,拷贝到你的电脑硬盘里。那么数据都是在哪些设备上的呢?键盘…...
结合大语言模型的机械臂抓取操作简单介绍
一、大语言模型与机械臂抓取的基本操作 1. 大语言模型简介 大语言模型是基于深度学习技术构建的自然语言处理模型,能够生成、理解和处理文本信息。这些模型通过训练大量的文本数据,学习语法、上下文和常识,能够执行多种任务,如文…...

Vivado - BD(差分时钟、简单分频、RESET、KEY)
目录 1. 简介 1.1 要点 1.2 buffer 介绍 2. vivado 工程 2.1 Block Design 2.2 IBUFDS 2.3 BUFGCE_DIV 2.4 Processor System Reset 2.5 key_mod 2.6 led_drv 3. 编译与调试 3.1 XDC 3.2 Debug 4. 总结 1. 简介 1.1 要点 了解 Utility Buffer v2.2 中的 Buffer…...

7--苍穹外卖-SpringBoot项目中套餐管理 详解(一)
前言 目录 新增套餐 需求分析和设计 代码开发 根据分类id查询菜品 Controller层 Service层 ServiceImpl层 Mapper层 DishMapper.xml 新增套餐 实体类 mapper层 Service层 ServiceImpl层 Mapper层 SetmealMapper.xml setmealDishMapper.xml 套餐分页查询 需求分…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...

Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
Python爬虫实战:研究Restkit库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001
qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类,直接把源文件拖进VS的项目里,然后VS卡住十秒,然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分,导致编译的时候找不到了。因…...
在ubuntu等linux系统上申请https证书
使用 Certbot 自动申请 安装 Certbot Certbot 是 Let’s Encrypt 官方推荐的自动化工具,支持多种操作系统和服务器环境。 在 Ubuntu/Debian 上: sudo apt update sudo apt install certbot申请证书 纯手动方式(不自动配置)&…...
Python打卡训练营学习记录Day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
scan_mode设计原则
scan_mode设计原则 在进行mtp controller设计时,基本功能设计完成后,需要设计scan_mode设计。 1、在进行scan_mode设计时,需要保证mtp处于standby模式,不会有擦写、编程动作。 2、只需要固定mtp datasheet说明的接口即可…...

二叉树-226.翻转链表-力扣(LeetCode)
一、题目解析 翻转可以理解为树的左右子树交换,从根到叶子节点,但是这里交换的是链接的指针,而不是单纯的交换值,当出现nullptr时,也是可以交换链接的,交换值的话就不行了。 二、算法原理 依旧的递归&…...