当前位置:网站首页>[code + 1] Yazid's freshman ball
[code + 1] Yazid's freshman ball
2021-08-08 00:30:56 【mrclr】
delivery
I took the original question in the competition , Gu Zige pushed out a very complex line segment tree , I didn't expect it to be a positive solution .
Our enumeration size is \(x\) Number of numbers , So if in the interval \([L, R]\) in ,\(x\) Meet the requirements of the topic , remember \(num[i]\) by \(1\) To \(i\) in \(x\) Number of occurrences of , So there are \(\frac{num[R] - num[L - 1]}{R - L + 1} > \frac1{2}\), Put it in order $$2num[R] - R > 2num[L - 1] - (L - 1)$$
So we make \(b[i] = 2num[i] - i\), It becomes to count \(b[j] < b[i](j < i)\) I've got a lot of them .
Use whatever data structure to maintain , For size \(x\) Statistics of the number of , It's about to reach \(O(n^2logn)\) Complexity .
But every time from \(1\) To \(n\) Of course not , So we thought , Can you just traverse \(x\) Position of appearance .
remember \(i\) by \(x\) The location of this occurrence ,\(nxt[i]\) by \(x\) The next place , So we have to find all the... Quickly \(j\), Satisfy \(b[j] < b[i], j < i, i \in [i, nxt[i] - 1]\).
about \((i, nxt[i] - 1]\) Medium \(b[i]\), Yes \(b[i] = b[i - 1] - 1\), So what you want to query is actually a continuous prefix and , namely \(sum[b[i]], sum[b[i]-1], \cdots, sum[b[i] - (nxt[i] - i - 1)]\).
Because there are still changes , Therefore, we are inspired to use the segment tree to maintain the prefix and , That is, each node maintains the sum of all numbers less than or equal to the right endpoint .
Then the above inquiry is equivalent to the interval \([b[i] - (nxt[i] - i - 1) - 1, b[i] - 1]\) The query .
And modify , If you add a number \(t\), Because it maintains prefixes and , To set the interval \([t, n]\) all \(1\). But now we should put \([i, nxt[i] - 1]\) All contributions are added to the segment tree , About to \([b[i], n],[b[i] - 1, n], \cdots, [b[i] - (nxt[i] - i), n]\) Add it all \(1\).
Think about it a little bit , Will find , In fact, it is the interval \([b[i] - (nxt[i] - i), b[i]]\) Add a first item as 1 A series of equal proportions , Then put the interval \([b[i] + 1, n]\) Add \(nxt[i] - i\). Therefore, the segment tree should support interval addition and interval addition arithmetic sequence , And sum intervals .
Add equal ratio sequence , Convert to absolute subscript , Maintaining a one-time function .
版权声明
本文为[mrclr]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210808003020469S.html
边栏推荐
- 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!