当前位置:网站首页>[Code+#1]Yazid 的新生舞会
[Code+#1]Yazid 的新生舞会
2021-08-08 00:30:28 【mrclr】
传送
这题比赛的时候考了原题,顾子哥推了出来一个挺复杂的线段树,没想到竟然是正解。
我们枚举大小为\(x\)的数,那么如果在区间\([L, R]\)中,\(x\)符合题目的条件,记\(num[i]\)为\(1\)到\(i\)中\(x\)的出现次数,那么有\(\frac{num[R] - num[L - 1]}{R - L + 1} > \frac1{2}\),整理得$$2num[R] - R > 2num[L - 1] - (L - 1)$$
所以我们令\(b[i] = 2num[i] - i\),就变成了要统计\(b[j] < b[i](j < i)\)的个数了。
随便用什么数据结构维护,对于大小为\(x\)的数的统计,大概能达到\(O(n^2logn)\)的复杂度。
但每次从\(1\)到\(n\)扫一遍当然不行,所以我们想,能不能只遍历\(x\)出现的位置。
记\(i\)为\(x\)这一次出现的位置,\(nxt[i]\)为\(x\)下一次出现的位置,那么我们要快速的找到所有的\(j\),满足\(b[j] < b[i], j < i, i \in [i, nxt[i] - 1]\).
对于\((i, nxt[i] - 1]\)中的\(b[i]\),有\(b[i] = b[i - 1] - 1\),那么要查询的实际是连续的一段前缀和,即\(sum[b[i]], sum[b[i]-1], \cdots, sum[b[i] - (nxt[i] - i - 1)]\).
因为还要有修改,遂启发我们用线段树维护前缀和,即每个节点维护小于等于右端点的所有数的和。
那么上述的询问就相当于对区间\([b[i] - (nxt[i] - i - 1) - 1, b[i] - 1]\)进行查询。
而修改,如果加入一个数\(t\),因为维护的是前缀和,要对区间\([t, n]\)都加\(1\)。但是现在我们应该把\([i, nxt[i] - 1]\)的贡献全部加入线段树中,即将区间\([b[i], n],[b[i] - 1, n], \cdots, [b[i] - (nxt[i] - i), n]\)全部加\(1\)。
稍微想一下,会发现,其实是将区间\([b[i] - (nxt[i] - i), b[i]]\)加一个首项为1的等比数列,再将区间\([b[i] + 1, n]\)加\(nxt[i] - i\).所以线段树要支持区间加和区间加等差数列,以及求区间和。
加等比数列,转换成绝对下标即可,维护一个一次函数而已。
版权声明
本文为[mrclr]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15234622/3310232
边栏推荐
- Fourth in the world! Wang Sicong installed a server "readily". Netizen: trench is inhuman
- [Tencent classroom] creator zero foundation immortal practice is online!
- 跟着华为,学数字化转型(3):模式创新
- 记一次接口慢查排查
- Follow Huawei and learn digital transformation (3): mode innovation
- Record an interface slow check and troubleshooting
- @Autowired的这些骚操作,你都知道吗?
- ss -h命令
- @Do you know all these operations of Autowired?
- 使用Yolo v5进行目标检测
猜你喜欢
-
Yazid的新生舞会(线段树)
-
当creator遇上protobufjs|孕育
-
Identify and stop the process that‘s listening on port 8080 or configure this application to listen
-
为什么要推荐大家学习字节码?
-
揭秘!价值百万的像素填色解决方案,想开发绘本应用的有福了!
-
[PyTroch系列-11]:PyTorch基础 - 张量Tensor元素的排序
-
[PyTroch系列-12]:PyTorch基础 - 张量Tensor线性运算(点乘、叉乘)
-
【环境篇】第 3 节 • Navicat 环境安装
-
预训练语言模型的前世今生 - 从Word Embedding到BERT
-
讲道理,只要你是一个爱折腾的程序员,毕业找工作真的不需要再花钱培训!
随机推荐
- 华南理工 | 基于生成式的低比特无数据量化
- 微信小程序授权位置和用户信息权限(防止用户禁止后无法使用位置信息)
- 一行代码快速实现今日头条 网易新闻焦点图自动循环轮播效果
- 因果涌现:数学理论揭示整体怎样大于部分之和
- 年收入百万美元AI科学家的烦恼
- API《为什么奥运会以五色环为标志?》数据源接口
- 用一张草图创建GAN模型,新手也能玩转,朱俊彦团队新研究入选ICCV 2021
- UIUC | 用于语言模型的课程学习
- SS - H command
- Target detection using Yolo V5
- Yazid's freshman ball (thread tree)
- When creator meets protobufjs 𞓜
- 我敢肯定!你还没用过一款代码神器,只属于Creator的用户!
- 小程序页面跳转&&文章详情页的实现&&markdown格式转化为wxml显示在小程序页面里
- 49个项目管理过程ITTO整理(详细)
- 49个项目管理过程ITTO整理(详细-文字版)
- 只是想虐下春丽,一不小心撸了台游戏机...
- Cocos论坛九问九答
- Identify and stop the process that‘s listening on port 8080 or configure this application to listen
- 超详细的I/O多路复用概念、常用I/O模型、系统调用等介绍
- Why recommend learning bytecode?
- SAP Commerce Cloud UI 的用户会话管理
- 以太坊 交易 data字段 内容是什么
- SAP CRM Fiori 应用 My Note 里创建 Note 失败的一个原因分析
- 当creator遇上protobufjs|pbkiller填坑历险记
- Uncover the secret! Millions of pixel color filling solutions. Blessed are those who want to develop picture book applications!
- [pytroch series - 11]: pytorch basis - ordering of tensor tensor elements
- [pytroch series - 12]: pytorch basis tensor tensor linear operation (point multiplication, cross multiplication)
- [environment] section 3 • Navicat environment installation
- The past and present life of pre training language model - from word embedding to Bert
- Make sense, as long as you are a tossing programmer, you really don't need to spend money on training to find a job after graduation!
- South China Technology | low bit no data quantization based on generative
- Wechat applet authorizes location and user information permissions (to prevent users from being unable to use location information after prohibition)
- One line of code can quickly realize the automatic circular rotation effect of today's headlines and Netease News focus map
- Causal emergence: mathematical theory reveals how the whole is greater than the sum of parts
- The troubles of AI scientists with an annual income of millions of dollars
- API "why is the Olympic Games marked by five color rings?" Data source interface
- Create a GaN model with a sketch, which can be played by novices. The new research of Zhu Junyan's team was selected into iccv 2021
- UIUC | course learning for language model
- I'm sure! You haven't used a code artifact yet. It only belongs to creator users!