首页 > 其他分享 >P3765 总统选举

P3765 总统选举

时间:2024-05-03 15:45:41浏览次数:16  
标签:二元 选举 总统 摩尔 给定 P3765 众数 区间

题意

给定一个序列,表示 \(n\) 个人每个人给 \(a_i\) 投了一票。

每次操作给定序列 \([l, r]\),求 \([l, r]\) 的众数。

若 \([l, r]\) 没有绝对众数则令该区间的众数为 \(p\),并将随后给定的 \(k\) 个整数,\(a_{s_1}, a_{s_2}, ... a_{s_k}\) 改为 \(p\)。

Sol

摩尔投票。

一句话总结,就是设二元组 \((x, y)\),表示当前数为 \(x\),权值为 \(y\)。

若合并两个二元组 \((x_1, y_1), (x_2, y_2)\) 取 \(y\) 较大的 \(x\),\(y\) 相减,若 \(x\) 相同,则 \(y\) 相加。

这个玩意显然是满足结合律的。

考虑使用线段树维护这个东西。

但是有个问题,摩尔投票保证若 区间有众数 则留下的一定是众数,若区间没有众数,求出来的不一定是众数。

可以考虑用一颗平衡树判断每一次操作的是否是区间的众数。

复杂度:\(O(n \log n)\)

标签:二元,选举,总统,摩尔,给定,P3765,众数,区间
From: https://www.cnblogs.com/cxqghzj/p/18171259

相关文章

  • Zookeeper的选举机制
    为什么要进行Leader选举?Leader主要作用是保证分布式数据一致性,即每个节点的存储的数据同步。遇到以下两种情况需要进行Leader选举服务器初始化启动服务器运行期间无法和Leader保持连接,Leader节点崩溃,逻辑时钟崩溃。服务器初始化时Leader选举Zookeeper由于其自身的性质,一般......
  • P8162 [JOI 2022 Final] 让我们赢得选举
    P8162[JOI2022Final]让我们赢得选举贪心+dp题目要求最小耗时,可以考虑贪心和dp。先考虑贪心。首先,假如我们此时有\(b\)个州得到了选票和协作者,那么下一次演讲一定是\(b\)个协作者和自己一起去同一个州演讲,时间为\(\frac{a_i/b_i}{b+1}\),这样我们的时间一定不会浪费掉。......
  • Zookeeper-Leader选举
    一、前言Zookeeper服务端集群启动,Leader选举是很重要的一部分。二、Leader选举2.1Leader选举概述Leader选举是保证分布式数据一致性的关键所在。当Zookeeper集群中的一台服务器出现以下两种情况之一时,需要进入Leader选举。(1)服务器初始化启动。(2)......
  • 【IT老齐071】Paxos选举算法
    【IT老齐072】全文检索执行原理https://lamport.azurewebsites.net/pubs/lamport-paxos.pdfPaxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法,使其获得2013年图灵奖。在Zookeeper中,通过Paxos算法选举出主节点,同时保证集群数据的强一致性(CP)......
  • 【IT老齐057】Raft选举算法
    【IT老齐057】Raft选举算法用途Raft算法是分布式系统开发首选的共识算法主要在分布式集群架构下进行领导者(主节点)的确认。比如现在流行的组件Etcd、Consul、Nacos、RocketMQ、RedisSentinel底层都是采用Raft算法来确认集群中的主节点,再通过主节点向其他节点下发指令......
  • mongoDB使用记录:副本集选举淘汰策略失效
    一个问题场景:业务请求查询数据库,当请求没有成功返回时(这里是数据库机器异常,表现是不返回请求结果,处于假死状态),业务挂起进入等待(WAIT),逻辑中断,表现为卡顿、持续加载中;高并发场景下,短时间内堆积的请求会大量占用发起数据库请求的机器的内存(风险一),大量业务卡顿异常;当数据库异常解决成......
  • repmgr选举原理
    从墨天轮上看到一篇非常详细的repmgr的选举原理文章https://www.modb.pro/db/17170614490157137921)很不幸,由于某种原因主库A节点down掉了2)B,C,D尝试等待重连主库A节点:checkingstateofnode1,Nof6attempts…3)连接超时后,BCD会各自进入选举的过程:由于D的location......
  • abc317D 选举总统
    题面:有n个区,第i个区有x[i]+y[i]个选民,其中x[i]支持A,y[i]支持B,支持人数多的一方获得该区的全部票数z[i],全部区的票数之和多者获胜,问至少还要多少选民从支持B改为支持A,才能让A胜出?范围:1<=n<=100;0<=x[i],y[i]<=1E9;x[i]+y[i]为奇数,z[i]>=1,z[i]之和为奇数且不超过1E5。思路:将各......
  • P1781 宇宙总统
    1.题目介绍题目描述地球历公元6036年,全宇宙准备竞选一个最贤能的人当总统,共有\(n\)个非凡拔尖的人竞选总统,现在票数已经统计完毕,请你算出谁能够当上总统。输入格式第一行为一个整数\(n\),代表竞选总统的人数。接下来有\(n\)行,分别为第一个候选人到第\(n\)个候选人的......
  • P1271 【深基9.例1】选举学生会
    1.题目介绍【深基9.例1】选举学生会题目描述学校正在选举学生会成员,有\(n\)(\(n\le999\))名候选人,每名候选人编号分别从\(1\)到\(n\),现在收集到了\(m\)(\(m\le2000000\))张选票,每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。输入格......