agc003E Sequential operations on Sequence
2024-10-07 21:57:26
题意:
有一个数字串S,初始长度为n,是1 2 3 4 …… n。
有m次操作,每次操作给你一个正整数a[i],你先把S无穷重复,然后把前a[i]截取出来成为新的S。
求m次操作后,每个数字在S中出现的次数。
$n,m \leq 10^5 , a[i] \leq 10^{18}$
首先明显要倒着做,正着不好做。
我们发现,对于$a$这个数组,如果存在$j$满足$j>i,a[j]<a[i]$,那么$a[i]$这个操作就是可以删掉的
这样处理过后,$a$就变成了一个递增的数组。
我们用$f[x]$表示第$x$个操作之后的序列,在最后的序列中,整个出现多少次。
倒着考虑每一个操作,假如我们考虑到了操作$X$。
我们设第$X$个操作前的序列为$P[X-1]$,第$X$个操作后的序列为$P[X]$
那么$P[X]$一定由几个完整的$P[X-1]$加上一段长度为$l$的$P[X-1]$的前缀(边角料)构成。
对于完整的部分,我们显然可以用$f[X]$直接转移到$f[X-1]$,主要是对于剩下长度为$l$的部分,单独考虑这一部分的贡献。
我们二分找到最靠右那个长度$\leq l$的$P[i]$,这个时候,这一部分的贡献,有一些可以完整的作用于$f[i]$上,然后还会剩下一段边角料
我们可以一直这样一直递归下去,到了最后特殊处理一下。
每次$l$都会$mod \ |P[i]|$,长度至少会减一半,所以复杂度是带2个log的,可以接受。
我一开始想这道题的时候,一直在想什么数据结构维护每一位的贡献,结果发现维护不来。
所以说,突破点在$f$这个数组的构造上,我们不一定要维护每一位的贡献,我们可以维护一个序列的贡献。
我太蠢啦。
最新文章
- (十五)使用Nexus创建Maven私服
- No.009:Palindrome Number
- Json序列化之.NET开源类库Newtonsoft.Json的研究
- 150923-碎觉要-PHP,Linux
- == 与 equals
- 夺命雷公狗---node.js---2node.js中的npm的常用命令
- J2EE、J2SE、J2ME
- Linux - 标准输入转换为标准输出 代码(C)
- WPF-24:绘制正多边形
- ios日历视图实现日期输入
- AlphaBlend參数BLENDFUNCTION
- 了解mongoDB存储结构
- 灵玖软件NLPIRParser智能文本聚类
- 第十二章 FTP服务器安装与配置
- 《mysql必知必会》学习_第17章_20180807_欢
- VS中生成时“sgen.exe”已退出,代码为 1解决办法
- QPS/TPS/并发量/系统吞吐量的概念
- ASP.NET MVC验证码演示
- Java jdk 8 新特性
- jsp版ueditor图片在线管理返回绝对路径