【题解】JZOJ3854 分组
JZOJ 3854
题意
有 n n n 个人,每个人有地位 r i r_i ri 和年龄 a i a_i ai,对于一个若干人组成的小组,定义其队长为地位最高的成员(若相等则取二者均可),其他成员的年龄与队长的差不能超过 k k k。 q q q 次询问,若将 x , y x,y x,y 安排在同一个小组,那么这个小组最多多少人。
题解
先预处理每个人当队长时小组最多有多少人。设这个值为 c n t i cnt_i cnti。
具体来说,按 r r r 排序,对于 i i i 需要求前面 i i i 个人有多少个人的年龄在 [ a i − k , a i + k ] [a_i-k,a_i+k] [ai−k,ai+k] 的区间内。用一个动态开点权值线段树即可。下标是年龄。
考虑对询问离线。不妨假设 r x ≤ r y r_x\le r_y rx≤ry,那么对于一个询问 i i i,能够包含 x i , y i x_i,y_i xi,yi 的队长的范围是 r ≥ r y i , max ( a x i , a y i ) − k ≤ a ≤ min ( a x i , a y i ) + k r\ge r_{y_i},\max (a_{x_i},a_{y_i}) - k\le a\le \min(a_{x_i},a_{y_i})+k r≥ryi,max(axi,ayi)−k≤a≤min(axi,ayi)+k。因为与 x , y x,y x,y 的年龄差要同时小于 k k k,所以选范围小的区间。
按 r y r_y ry 为关键值将询问从大到小排序。然后一个动态开点权值线段树,下标是年龄,叶子节点存储 c n t i cnt_i cnti。这样对于一个询问,只需要查找在 [ max ( a x i , a y i ) − k , min ( a x i , a y i ) + k ] [\max (a_{x_i},a_{y_i}) - k,\min(a_{x_i},a_{y_i})+k] [max(axi,ayi)−k,min(axi,ayi)+k] 区间内的最大值即可。
时间复杂度 O ( n log w ) O(n\log w) O(nlogw)。
实现
记得判 -1
。注意输入的标号是排序前的标号,要处理一下。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, W = 1e9;
int n, K, Q, ans[N], vp[N], cnt[N];
int tr[N << 4], mx[N << 4], rt1 = 0, rt2 = 0, tot1 = 0, tot2 = 0, ls1[N << 4], rs1[N << 4], ls2[N << 4], rs2[N << 4];
struct mem {int r, ag, id;bool operator< (const mem &T) const { return r < T.r; }
} a[N];
struct Query {int x, y, id;bool operator< (const Query &T) const { return a[y].r > a[T.y].r; }
} q[N];
void upd1(int &rt, int x, int y, int pos, int val) {if (!rt) rt = ++tot1;if (x == y) { tr[rt] += val; return; }int mid = x + y >> 1;if (pos <= mid) upd1(ls1[rt], x, mid, pos, val);else upd1(rs1[rt], mid + 1, y, pos, val);tr[rt] = tr[ls1[rt]] + tr[rs1[rt]];
}
int qry1(int rt, int x, int y, int l, int r) {if (l > y || r < x || !rt) return 0;if (l <= x && y <= r) return tr[rt];int mid = x + y >> 1;return qry1(ls1[rt], x, mid, l, r) + qry1(rs1[rt], mid + 1, y, l, r);
}
void upd2(int &rt, int x, int y, int pos, int val) {if (!rt) rt = ++tot2;if (x == y) { mx[rt] = max(mx[rt], val); return; }int mid = x + y >> 1;if (pos <= mid) upd2(ls2[rt], x, mid, pos, val);else upd2(rs2[rt], mid + 1, y, pos, val);mx[rt] = max(mx[ls2[rt]], mx[rs2[rt]]);
}
int qry2(int rt, int x, int y, int l, int r) {if (l > y || r < x || !rt) return 0;if (l <= x && y <= r) return mx[rt];int mid = x + y >> 1;return max(qry2(ls2[rt], x, mid, l, r), qry2(rs2[rt], mid + 1, y, l, r));
}
int main() {scanf("%d%d", &n, &K);for (int i = 1; i <= n; i++) scanf("%d", &a[i].r), a[i].id = i;for (int i = 1; i <= n; i++) scanf("%d", &a[i].ag);sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++) vp[a[i].id] = i;for (int i = 1; i <= n; ) {int j = i;while (a[j].r == a[j + 1].r) upd1(rt1, 1, W, a[j].ag, 1), j++;upd1(rt1, 1, W, a[j].ag, 1);for (; i <= j; i++) cnt[i] = qry1(rt1, 1, W, a[i].ag - K, a[i].ag + K);}scanf("%d", &Q);for (int i = 1; i <= Q; i++) {scanf("%d%d", &q[i].x, &q[i].y), q[i].x = vp[q[i].x], q[i].y = vp[q[i].y], q[i].id = i;if (q[i].x > q[i].y) swap(q[i].x, q[i].y);}sort(q + 1, q + Q + 1);int k = n;for (int i = 1; i <= Q; i++) {while (q[i].y <= k) upd2(rt2, 1, W, a[k].ag, cnt[k]), k--;ans[q[i].id] = qry2(rt2, 1, W, max(a[q[i].x].ag, a[q[i].y].ag) - K, min(a[q[i].x].ag, a[q[i].y].ag) + K);if (ans[q[i].id] < 2) ans[q[i].id] = -1;}for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);return 0;
}
相关文章:
【题解】JZOJ3854 分组
JZOJ 3854 题意 有 n n n 个人,每个人有地位 r i r_i ri 和年龄 a i a_i ai,对于一个若干人组成的小组,定义其队长为地位最高的成员(若相等则取二者均可),其他成员的年龄与队长的差不能超过 k k …...
区块链实验室(26) - 区块链期刊Blockchain: Research and Applications
Elsevier出版物“Blockchain: Research and Applications”是浙江大学编审的期刊。该期刊自2020年创刊,并出版第1卷。每年出版4期,最新期是第4卷第3期(2023年9月)。 目前没有官方的IF,Elsevier的引用因子Citescore是6.4。 虽然是新刊…...
【学习笔记】[ARC153F] Tri-Colored Paths
假设三种颜色的边都存在,并且不存在这样的路径 首先观察到,对于一个简单环上的边,颜色一定相同 因此,考虑建立圆方树,问题转化为圆方树上的 D P DP DP问题。限制是对于方点所连接的边,必须涂上相同的颜色…...
基于SSM的实习管理系统
基于SSM的实习管理系统、前后端分离 开发语言:Java数据库:MySQL技术:SpringSpringMVCMyBatisVue工具:IDEA/Ecilpse、Navicat、Maven 系统展示 管理员界面 教师 学生 研究背景 基于SSM的实习管理系统是一个基于Spring、Spring…...
在Vue中通过ElementUI构建前端页面【登录,注册】,在IEDA构建后端实现前后端分离
一.ElementUI组件入门 1.对于ElementUI的理解 是一套基于 Vue.js 的开源UI组件库,提供了丰富的可复用组件,可以帮助开发者快速构建美观、易用的前端界面 2.Element UI 的特点和优势 多样化的组件:Element UI 提供了众多常用的基础组件&#…...
TX2 open ttyTHS2
TX2 open ttyTHS2 #冷风那个吹# 于 2019-04-01 14:10:43 发布 1749 收藏 6 分类专栏: 平时问题积累 TX2 版权 平时问题积累 同时被 2 个专栏收录 22 篇文章0 订阅 订阅专栏 TX2 30 篇文章8 订阅 订阅专栏 TX2上有5个串口,但是ttyTHS1是调试串口,ttyTHS3是蓝牙,ttyTHS…...
conan入门(二十八):解决conan 1.60.0下 arch64-linux-gnu交叉编译openssl/3.1.2报错问题
上一篇博客《conan入门(二十七):因profile [env]字段废弃导致的boost/1.81.0 在aarch64-linux-gnu下交叉编译失败》解决了conan 1.60.0交叉编译boost/1.80.1的问题后,我继续交叉编译openssl/3.1.2时又报错了 conan install openssl/3.1.2 -pr:h aarch64-linux-gnu.…...
Xcode 15 运行<iOS 14, 启动崩溃问题
如题. Xcode 15 启动 < iOS 14(没具体验证过, 我的问题设备是iOS 13.7)真机设备 出现启动崩溃 解决方案: Build Settings -> Other Linker Flags -> Add -> -ld64...
HTTPS协议概述
HTTPS(Hypertext Transfer Protocol over Secure Socket Layer,基于安全套接字层的超文本传输协议),是以安全为目标的HTTP通道,简单讲是HTTP的安全版。即HTTP下加入SSL层,HTTPS的安全基础是SSL,…...
jmeterbeanshell调用jsonpath获取对应值
1.jmeter 新建线程组、Java Request、BeanShell Assertion、View Results Tree 2、在BeanShell Assertion中贴入代码: import org.apache.jmeter.extractor.json.jsonpath.JSONManager; import java.util.List; JSONManager js new JSONManager(); String jsonStr…...
C++中实现雪花算法来在秒级以及毫秒及时间内生成唯一id
1、雪花算法原理 雪花算法(Snowflake Algorithm)是一种用于生成唯一ID的算法,通常用于分布式系统中,以确保生成的ID在整个分布式系统中具有唯一性。它的名称来源于雪花的形状,因为生成的ID通常是64位的整数࿰…...
OPTEE Gprof(GNU profile)
安全之安全(security)博客目录导读 OPTEE调试技术汇总 目录 一、序言 二、Gprof使用 三、Gprof实现 1、Call graph information 2、PC distribution over time 一、序言 本文描述了如何使用gprof对TA进行概要分析。 配置选项CFG_TA_GPROF_SUPPORTy使OP-TEE能够从在用户模…...
MySQL 事务的操作指南(事务篇 二)
基本操作 事务的提交方式:自动提交(autocommit1)和手动提交(autocommit0) 查询和修改事务提交方式: -- 查看事务提交方式(标识表示这是个系统变量) select autocommit ;-- 修改事务提交方式为自动提交 …...
Oracle 查询 SQL 语句
目录 1. Oracle 查询 SQL 语句1.1. 性能查询常用 SQL1.1.1. 查询最慢的 SQL1.1.2. 列出使用频率最高的 5 个查询1.1.3. 消耗磁盘读取最多的 sql top51.1.4. 找出需要大量缓冲读取(逻辑读)操作的查询1.1.5. 查询每天执行慢的 SQL1.1.6. 从 V$SQLAREA 中查询最占用资源的查询1.1.…...
gin 基本使用
gin 初体验 import ("net/http""github.com/gin-gonic/gin" )func main() {r : gin.Default()r.GET("/ping", func(c *gin.Context) {c.JSON(http.StatusOK, gin.H{"message": "pong",})})r.Run() }gin 路由接受一个 type …...
8月最新修正版风车IM即时聊天通讯源码+搭建教程
8月最新修正版风车IM即时聊天通讯源码搭建教程。风车 IM没啥好说的很多人在找,IM的天花板了,知道的在找的都知道它的价值,开版好像就要29999,后端加密已解,可自己再加密,可反编译出后端项目源码,已增加启动后端需要google auth双重验证,pc端 web端 wap端 android端 ios端 都有 …...
NSDT孪生场景编辑器系统介绍
一、产品背景 数字孪生的建设流程涉及建模、美术、程序、仿真等多种人才的协同作业,人力要求高,实施成本高,建设周期长。如何让小型团队甚至一个人就可以完成数字孪生的开发,是数字孪生工具链要解决的重要问题。考虑到数字孪生复杂…...
3D WEB轻量化引擎HOOPS助力3D测量应用蓬勃发展:效率、精度显著提升
在3D开发工具领域,Tech Soft 3D打造的HOOPS SDK已经崭露头角,成为了全球领先的3D领域开发工具提供商。HOOPS SDK包括四种不同的3D软件开发工具,已成为行业的翘楚。 其中,HOOPS Exchange以其CAD数据转换的能力脱颖而出,…...
【Orange Pi】Orange Pi5 Plus 安装记录
官网:Orange Pi - Orangepi 主控芯片:Rockchip RK3588(8nm LP制程)NPU:内嵌的 NPU 支持INT4/INT8/INT16/FP16混合运算,算力高达 6Top支持的操作系统: Orangepi OS(Droid)Orangepi O…...
NLP 项目:维基百科文章爬虫和分类 - 语料库阅读器
塞巴斯蒂安 一、说明 自然语言处理是机器学习和人工智能的一个迷人领域。这篇博客文章启动了一个具体的 NLP 项目,涉及使用维基百科文章进行聚类、分类和知识提取。灵感和一般方法源自《Applied Text Analysis with Python》一书。 在接下来的文章中,我将…...
查看吾托帮88.47的docker里的tomcat日志
步骤如下 (1)ssh (2)ssh root192.168.88.47 等待输入密码:fytest (3)pwd #注释:输出/root (4)docker exec -it wetoband_deploy /bin/bash #注释࿱…...
衷心 祝愿
达之云衷心祝愿您,中秋国庆双节快乐,阖家幸福!感谢您们一直以来对达之云的关注与支持。 双节来临之际,达之云发布全新产品——达之云CDP客户数据平台(Dazdata CDP),致力于为中小企业提供互联网营…...
表单中某一项点击添加和删除
<!-- 特殊表单 --><div v-for"(item, index) in form.fwzb" :key"indexfwzb" style"height: 102px"><el-form-item label"经度:" class"form-style":prop"fwzb. index .lon":rules&q…...
深信服安全GPT 2.0升级,开启安全运营“智能驾驶”旅程
9月22日,深信服对外展示安全GPT落地成果与2.0升级能力。来自各行业权威嘉宾代表:美的集团首席信息安全官(CISO)兼软件工程院院长、欧洲科学院院士(MAE)、IEEE Fellow、IET Fellow、ACM杰出科学家、AAIA Fel…...
【C++】STL之list深度剖析及模拟实现
目录 前言 一、list 的使用 1、构造函数 2、迭代器 3、增删查改 4、其他函数使用 二、list 的模拟实现 1、节点的创建 2、push_back 和 push_front 3、普通迭代器 4、const 迭代器 5、增删查改(insert、erase、pop_back、pop_front) 6、构造函数和析构函数 6.1、默认构造…...
解释器风格架构C# 代码
/*解释器风格架构是一种基于组件的设计架构,它将应用程序分解为一系列组件,每个组件负责处理特定的任务。这种架构有助于提高代码的可维护性和可扩展性。以下是如何使用C#实现解释器风格架构的步骤:定义组件:首先,定义…...
第七天:gec6818开发板QT和Ubuntu中QT安装连接sqlite3数据库驱动环境保姆教程
sqlite3数据库简介 帮助文档 SQL Programming 大多数关系型数的操作步骤:1)连接数据库 多数关系型数据库都是C/S模型 (Client/Server)sqlite3是一个本地的单文件关系型数据库,同样也有“连接”的过程 2)操作数据库 作为程序员&am…...
自制网页。
文章目录 注:代码中图片等素材均来自网络,侵删 20230920_213831 index.html <!DOCTYPE html> <html lang="en"> <head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-…...
MySQL单表查询和多表查询
一、单表查询 素材: 表名:worker-- 表中字段均为中文,比如 部门号 工资 职工号 参加工作等 CREATE TABLE worker (部门号 int(11) NOT NULL,职工号 int(11) NOT NULL,工作时间 date NOT NULL,工资 float(8,2) NOT NULL,政治面貌 varchar(10)…...
蓝桥等考Python组别四级006
第一部分:选择题 1、Python L4 (15分) 在Python中,符号“\n”代表( )。 换行空格退格注释正确答案:A 2、Python L4 (15分) 已知大写字母A的ASCII码值为…...
华为网站建设/营销号
转载请注明地址(http://blog.csdn.net/xinzhangyanxiang/article/details/8522078) 学习概率的时候,大家一定都学过马尔科夫模型吧,当时就觉得很有意思,后来看了数学之美之隐马模型在自然语言处理中的应用后࿰…...
网站建设服务属于信息技术服务吗/关键词在线播放免费
在数据仓库中的转换和装载过程中,经常会使用MERGE语句,这里简单总结一下。 MERGE 语句是Oracle9i新增的语法,用来合并UPDATE和INSERT语句。通过MERGE语句,根据一张表或子查询的连接条件对另外一张表进行查询,连接条件匹…...
网站建设提成/电商培训心得
一、阿里云私有docker仓库管理指南 登录阿里云Docker Registry $ sudo docker login --username白衣卿相2744 registry.cn-shanghai.aliyuncs.com用于登录的用户名为阿里云账号全名 密码为开通服务时设置的密码**(点击查看)** 您可以在访问凭证…...
系部网站开发计划/全面落实疫情防控优化措施
走进异步编程的世界 - 在 GUI 中执行异步操作 【博主】反骨仔 【原文地址】http://www.cnblogs.com/liqingwen/p/5877042.html 序 这是继《开始接触 async/await 异步编程》、《走进异步编程的世界 - 剖析异步方法》后的第三篇。主要介绍在 WinForm 中如何执行异步操作。 目…...
北京注册公司代理机构/星沙网站优化seo
leetcode第377题组合总数 **思路:**动态规划 一眼看上去就是动态规划完全背包问题,凑零钱里面说到 先遍历物品在遍历背包是求组合先遍历背包在遍历物品是求排列没什么可说的,还算是比较合适吧! class Solution {public int combinationSu…...
嘉兴市建设教育网站/企业官网怎么做
1. 仅更新单个库 只想更新某个特定的库,不想更新它的所有依赖,很简单: composer update foo/bar 此外,这个技巧还可以用来解决“警告信息问题”。你一定见过这样的警告信息: Warning: The lock file is not up to date…...