首页/新闻资讯/正文详情

洛谷 P3567:[POI 2014] KUR-Couriers ← 主席树

发布时间:2026/11/19 1:57:56 来源:云帆数科 栏目:资讯中心
洛谷 P3567:[POI 2014] KUR-Couriers ← 主席树
【题目来源】https://www.luogu.com.cn/problem/P3567【题目描述】Byteasar 在卖电脑游戏的 BAJ 公司上班。BAJ 公司和多家快递公司合作由这些快递公司将 BAJ 公司销售的游戏送给客户。Byteasar 正在审查 BAJ 公司与快递公司的合作情况。他有一份连续的包裹记录每个包裹都注明了负责配送的快递公司。他想确认没有任何一家快递公司比其他的具有不公平的优势。如果在某个时间段内某家快递公司配送了一半以上的包裹我们就说它在该时间段内占主导地位。Byteasar 想要知道在某些特定的时间段内哪家快递公司占主导地位如果存在的话。来帮 Byteasar 解决这个问题吧请编写一个程序判断在给定时间段内占主导地位的快递公司或者判断不存在这样的公司。【输入格式】第一行包含两个整数 n,m用一个空格分隔分别表示 BAJ 公司发货的包裹总数以及需要查询占主导地位的快递公司的时间段数量。第二行包含 n 个整数 a1,a2,…,an用单个空格隔开ai 表示配送第 i 个包裹的快递公司编号按照配送时间排序。接下来的 m 行每行指定对某个时间段的询问。每个询问包含两个整数 l 和 r用一个空格分隔。这意味着需要确定在第 l 个包裹到第 r 个包裹包含这两个包裹的发货期间占主导地位的快递公司。【输出格式】输出 m 行每行包含一个整数表示对于每个询问的时间段占主导地位公司的编号如果不存在这样的公司则输出 0。【输入样例】7 51 1 3 2 3 4 31 31 43 71 76 6【输出样例】10304【数据范围】对于所有数据1≤n,m≤5×10^51≤ai≤n。【算法分析】● 简化题意 给一个长度为 n 的正整数序列 a。共有 m 组询问每次询问一个区间 [l,r]是否存在一个数在 [l,r] 中出现的次数严格大于一半。如果存在输出这个数否则输出 0。● 复用“洛谷 P3834 → https://blog.csdn.net/hnjzsyjyj/article/details/169217793”框架只改 query 里面一点点不用新知识点。【算法代码】#include bits/stdc.h using namespace std; const int N5e55; int root[N],a[N],tot; vectorint v; struct Node { int L,R,cnt; } tr[N*40]; int getid(int x) { return lower_bound(v.begin(),v.end(),x)-v.begin()1; } int build(int le,int ri) { int ptot; if(leri) return p; int mid(leri)/2; tr[p].Lbuild(le,mid); tr[p].Rbuild(mid1,ri); return p; } int update(int pre,int le,int ri,int x) { int ptot; tr[p]tr[pre]; if(leri) { tr[p].cnt; return p; } int mid(leri)/2; if(xmid) tr[p].Lupdate(tr[pre].L,le,mid,x); else tr[p].Rupdate(tr[pre].R,mid1,ri,x); tr[p].cnttr[tr[p].L].cnttr[tr[p].R].cnt; return p; } int query(int u,int v,int le,int ri,int k) { if(leri) return le; int mid(leri)/2; int leftcnttr[tr[v].L].cnt-tr[tr[u].L].cnt; int rightcnttr[tr[v].R].cnt-tr[tr[u].R].cnt; if(leftcntk) return query(tr[u].L,tr[v].L,le,mid,k); if(rightcntk) return query(tr[u].R,tr[v].R,mid1,ri,k); return 0; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cinnm; for(int i1; in; i) { cina[i]; v.push_back(a[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); int lenv.size(); root[0]build(1,len); for(int i1; in; i) { root[i]update(root[i-1],1,len,getid(a[i])); } while(m--) { int le,ri; cinleri; int k(ri-le1)/2; int idquery(root[le-1],root[ri],1,len,k); if(id) coutv[id-1]\n; else cout0\n; } return 0; } /* in: 7 5 1 1 3 2 3 4 3 1 3 1 4 3 7 1 7 6 6 out: 1 0 3 0 4 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/169217793

相关推荐

CDGA 数据治理工程师认证备考指南:一文搭建完整学习框架
CDGA 数据治理工程师认证备考指南:一文搭建完整学习框架

目录CDGA 数据治理工程师认证备考指南:一文搭建完整学习框架一、为什么要考 CDGA?二、先搞清楚:CDGA 考什么?2.1 主要参考教材2.2 考试形式与基本规则2.3 CDGA 的核心考察逻辑三、CDGA 知识体系全景图:17 个知识领域3.… · 2026/11/13 10:53:50

第十篇:《全文检索:tsvector、tsquery 与中文分词》
第十篇:《全文检索:tsvector、tsquery 与中文分词》

在上一篇文章中,我们通过分区表实现了“分而治之”——查询只扫描目标分区,旧数据用 DETACH 而非 DELETE 来清理。但分区解决的是数据规模问题,而不是搜索质量问题。当用户输入“数据库性能”时,如果底层用的是 LIKE ‘%数据库性能… · 2026/11/14 12:23:41

智能划词翻译产品介绍和使用指南
智能划词翻译产品介绍和使用指南

适用于 Microsoft Word 的 Windows 划词翻译工具智能划词翻译是一款面向 Windows 桌面版 Microsoft Word 的轻量工具。程序启动后常驻系统后台,在 Word 中选中英文或中文,再按下 Ctrl 和 Alt,即可在鼠标附近查看译文。无需安装浏览器插件&… · 2026/11/13 22:02:01

长顺电工证在哪考怎么报名怕交钱还白费?
长顺电工证在哪考怎么报名怕交钱还白费?

长顺电工证在哪考怎么报名怕交钱还白费? 怕考不过白交培训费?长顺电工证在哪考怎么报名?很多人在考电工证时,总担心钱花了证没拿到,或者学了也没用,其实这些问题都源于不了解流程和报考细节。如果你正打算报考电工证,这篇内容能帮你少走弯路,搞清楚报… · 2026/11/19 1:57:35

电工证查询进不了怎么考?保姆级教程教你一招搞定
电工证查询进不了怎么考?保姆级教程教你一招搞定

电工证查询进不了怎么考?保姆级教程教你一招搞定 急需特种作业证才能上岗找工作,偏偏电工证查询进不了,这事儿可真让人头疼。你不是一个人在战斗,身边很多人也遇到过类似问题。别急,这篇保姆级教程,从报名流程、考试内容、注意事项到证书变更,都给你安… · 2026/11/19 1:57:35

相城区在哪考电工证啊网上查询过期复审全攻略
相城区在哪考电工证啊网上查询过期复审全攻略

相城区在哪考电工证啊网上查询过期复审全攻略 证书过期了不知道怎么复审延期?别慌,网上查询就能搞定。很多电工在日常工作中遇到证书即将到期或者已经过期的情况,却不知道如何操作,白白影响了工作和项目进度。其实,只要掌握正确的流程,复审和延期并不难… · 2026/11/19 1:57:35

上海住建部电工证通过率揭秘:外省证怎么转过来?
上海住建部电工证通过率揭秘:外省证怎么转过来?

上海住建部电工证通过率揭秘:外省证怎么转过来? 之前考的证在外省能不能转过来?这是很多在外地打工的电工朋友最关心的问题,尤其是已经拿到低压电工证、高压电工证,但又打算在上海发展的朋友。现在上海市对特种作业操作证的管理越来越规范,很多人对… · 2026/11/19 1:57:35

重庆电工证在哪报名保姆级教程:急需特种作业证才能上岗找工作
重庆电工证在哪报名保姆级教程:急需特种作业证才能上岗找工作

重庆电工证在哪报名保姆级教程:急需特种作业证才能上岗找工作 你是不是正在为找工作发愁,但又苦于没有特种作业证?别急,今天这篇保姆级教程就带你从零开始搞懂【重庆电工证在哪报名】,帮你快速拿证上岗,别再被门槛拦住脚步。… · 2026/11/19 1:57:35

电工证到哪儿考2026河南最新政策解读与避坑指南
电工证到哪儿考2026河南最新政策解读与避坑指南

电工证到哪儿考2026河南最新政策解读与避坑指南 你是不是也担心学历不高怕报不上名?其实很多工友跟我一样,初中毕业也能考电工证,关键看的是你有没有实践经验。2026年河南最新政策已经出台,对电工证的报考条件、流程、考试内容都有了新的变化,我… · 2026/11/19 1:56:35

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/18 8:19:55

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/18 8:19:53

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/18 14:38:14

姑苏区哪里考电工证好考前押题怎么找
姑苏区哪里考电工证好考前押题怎么找

姑苏区哪里考电工证好考前押题怎么找 工地太忙根本没时间复习考试,电工证考前还总找不到靠谱的 考前押题 资源,真让人头疼。如果你也是在苏州姑苏区从事建筑或电力行业的,那这些建议你一定要看完。 为什么姑苏区考电工证的人这么多?… · 2026/11/19 0:00:12

罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南
罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南

罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南 之前考的证在外省能不能转过来?这几乎是每个特种作业证书持有者都会遇到的问题,特别是像你这样已经在外地工作多年,想回老家罗定发展或者重新规划职业路径的人。别急,今天就给你一条清晰的路… · 2026/11/19 0:00:12

罗定能考电工证吗 电工证含金量到底有多少?
罗定能考电工证吗 电工证含金量到底有多少?

罗定能考电工证吗 电工证含金量到底有多少? 之前考的证在外省能不能转过来,这几乎是每个准备考电工证的朋友最先想到的问题。特别是在罗定这样的地方,很多人的电工证都是在外地考的,现在想在当地继续使用,但不知道怎么办。实际上,电工证的 含金量… · 2026/11/19 0:00:12

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 0:22:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码