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

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+11] 的代表集暴力即可,其中 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 条边的图&#xff0c;有 q q q 次询问&#xff0c;每次询问一个 [ l , r ] [l,r] [l,r] 的区间&#xff0c;求将 n n n 个点分为两个部分后&#xff0c;编号在 [ l , r ] [l,r] [l,r] 内的边中&#xff0c;两端点属于同一部分的…...

高空抛物AI检测算法:精准防控,技术革新守护城市安全

近年来&#xff0c;随着城市化进程的加速&#xff0c;高楼大厦如雨后春笋般涌现&#xff0c;但随之而来的高空抛物问题却成为城市管理的一大难题。高空抛物不仅严重威胁行人的安全&#xff0c;还可能引发法律纠纷和社会问题。为了有效预防和减少高空抛物事件的发生&#xff0c;…...

html+css+js实现Collapse 折叠面板

实现效果&#xff1a; HTML部分 <div class"collapse"><ul><li><div class"header"><h4>一致性 Consistency</h4><span class"iconfont icon-jiantou"></span></div><div class"…...

RM服务器研究(一)

客户端默认端口是10100&#xff1a; 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 配置

调度中心&#xff1a; 负责管理调度信息&#xff0c;按照调度配置发出调度请求&#xff0c;自身不承担业务代码&#xff1b; 主要职责为执行器管理、任务管理、监控运维、日志管理等 任务执行器&#xff1a; 负责接收调度请求并执行任务逻辑&#xff1b; 主要职责是执行任…...

国内动态短效sk5

HTTP爬虫代理,软件测试&#xff0c; 动态转发IP方案&#xff0c;全高匿名&#xff0c;私密IP&#xff0c;固定网关将您每次请求的HTTP重定向到不同的后端IP&#xff0c;支持API;指路小熊IP https://www.xiaoxiongip.com?fromqkJWgD可测...

【路径规划】路径平滑算法,A星算法拐点的圆弧化处理

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

【寻找one piece的算法之路】——双指针算法!他与她是否会相遇呢?

&#x1f490;个人主页&#xff1a;初晴~ &#x1f4da;相关专栏&#xff1a;寻找one piece的刷题之路 什么是双指针算法 双指针算法是一种常用的编程技巧&#xff0c;尤其在处理数组和字符串问题时非常有效。这种方法的核心思想是使用两个指针来遍历数据结构&#xff0c;这两…...

UFS 3.1架构简介

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

注册安全分析报告:科研诚信查询平台无验证方式导致安全隐患

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…...

04.useTitle

在 React 应用中,动态更新页面标题是提升用户体验的一个重要方面。它可以让用户更清楚地知道当前页面的内容或状态,特别是在单页应用(SPA)中。useTitle 钩子提供了一种简单而有效的方式来管理文档标题。以下是如何实现和使用这个自定义钩子: const useTitle = title =>…...

ROS2中的srv、action、发布订阅三种方式

ROS2中的srv、action、发布订阅三种方式 以下是ROS2中srv、action、发布订阅三种方式的差异和使用场景的表格形式呈现&#xff1a; 特性/方式srv&#xff08;服务&#xff09;action&#xff08;动作&#xff09;发布订阅&#xff08;Publish-Subscribe&#xff09;通信模式请…...

HarmonyOS/OpenHarmony 自定义弹窗页面级层级控制解决方案

关键词&#xff1a;CuntomDialog自定义弹窗、SubWindow子窗口、页面级、弹窗层级控制、鸿蒙、弹窗展示层级异常 问题存在API版本&#xff1a;API10 - API12&#xff08;该问题已反馈&#xff0c;期望后续官方能增加页面级控制能力&#xff09; 在正常的鸿蒙app开发过程中&…...

C/C++进阶(一)--内存管理

更多精彩内容..... &#x1f389;❤️播主の主页✨&#x1f618; Stark、-CSDN博客 本文所在专栏&#xff1a; 学习专栏C语言_Stark、的博客-CSDN博客 其它专栏&#xff1a; 数据结构与算法_Stark、的博客-CSDN博客 ​​​​​​项目实战C系列_Stark、的博客-CSDN博客 座右铭&a…...

docker-compose 快速部署clickhouse集群

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

闯关训练三:Git 基础知识

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

Java--IO基本流

IO流 概述 生活中&#xff0c;你肯定经历过这样的场景。当你编辑一个文本文件&#xff0c;忘记了ctrls &#xff0c;可能文件就白白编辑了。当你电脑上插入一个U盘&#xff0c;可以把一个视频&#xff0c;拷贝到你的电脑硬盘里。那么数据都是在哪些设备上的呢&#xff1f;键盘…...

结合大语言模型的机械臂抓取操作简单介绍

一、大语言模型与机械臂抓取的基本操作 1. 大语言模型简介 大语言模型是基于深度学习技术构建的自然语言处理模型&#xff0c;能够生成、理解和处理文本信息。这些模型通过训练大量的文本数据&#xff0c;学习语法、上下文和常识&#xff0c;能够执行多种任务&#xff0c;如文…...

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主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Module Federation 和 Native Federation 的比较

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

优选算法第十二讲:队列 + 宽搜 优先级队列

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

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;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 起因是添加一个新的控件类&#xff0c;直接把源文件拖进VS的项目里&#xff0c;然后VS卡住十秒&#xff0c;然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分&#xff0c;导致编译的时候找不到了。因…...

在ubuntu等linux系统上申请https证书

使用 Certbot 自动申请 安装 Certbot Certbot 是 Let’s Encrypt 官方推荐的自动化工具&#xff0c;支持多种操作系统和服务器环境。 在 Ubuntu/Debian 上&#xff1a; sudo apt update sudo apt install certbot申请证书 纯手动方式&#xff08;不自动配置&#xff09;&…...

Python打卡训练营学习记录Day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

scan_mode设计原则

scan_mode设计原则 在进行mtp controller设计时&#xff0c;基本功能设计完成后&#xff0c;需要设计scan_mode设计。 1、在进行scan_mode设计时&#xff0c;需要保证mtp处于standby模式&#xff0c;不会有擦写、编程动作。 2、只需要固定mtp datasheet说明的接口即可&#xf…...

二叉树-226.翻转链表-力扣(LeetCode)

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