CF1098E Fedya the Potter
CF1098E Fedya the Potter
题意:有一个序列\(A\)。
对所有\(1\leq l\leq r\leq |A|\),将\(\gcd_{i=l}^{r}A_i\)加入\(B\)中。
然后将\(B\)从小到大排序。
对所有\(1\leq l\leq r\leq |B|\),将\(\sum_{i=l}^{r}B_i\)加入\(C\)中。
求\(C\)的中位数,即\(C_{\lfloor\frac{|C|}{2}\rfloor}\)。
\(n\leq 50000,A_i\leq 100000\)。
求中位数见得多了就可以知道要先二分答案,然后求\(C\)中\(\leq M\)的数的数量。
先找一下\(B\)的性质。由\(\gcd\)的一套理论可以知道\(B\)中不会超过\(n\log V\)个不同的数(当然这个题有值域的限制,这个就没用了)
现在要求\(B\)中和\(\leq M\)的段数。如果\(B\)长度短可以双指针求,但是\(B\)长度是\(O(n^2)\)的。
然而因为\(B\)中不同元素不多,还是可以双指针
双指针时细节什么的可以看代码,总之现在问题变成了:
左边有\(sa\)个数\(a\),右边有\(sb\)个数\(b\),中间数和为\(S\)。
你要选一个子段,还是要满足和\(\leq M\),而且\(a\)和\(b\)都至少要选到一个。
列出一个naive的式子:
\(\sum_{i=1}^{sa}\sum_{j=1}^{sb}[ai+bj+S\leq M]\)
稍作变换:
\(\sum_{i=1}^{sa}\sum_{j=1}^{sb}[j\leq\frac{M-S-ai}{b}]\)
\(\sum_{i=1}^{sa}\min(sb,\max(0,\lfloor\frac{M-S-ai}{b}\rfloor))\)
\(\sum_{i=1}^{sa}\max(0,\lfloor\frac{M-S-ai}{b}\rfloor)-\sum_{i=1}^{sa}\max(0,\lfloor\frac{M-S-ai-sb}{b}\rfloor)\)
那么问题又变成了,求
\(\sum_{i=0}^n\max(0,\lfloor\frac{ai+b}{c}\rfloor)\)
(注意因为类欧是从\(0\)开始的这里也是\(0\)开始)
这就是一个典型的类欧了。设\(F(n,a,b,c)=\sum_{i=0}^n\max(0,\lfloor\frac{ai+b}{c}\rfloor)\)。
求法就是一个大讨论:
首先考虑将\(a,b\)转成正数。
- 如果\(a<0\),\(F(n,a,b,c)=F(n,-a,b+na,c)\)
- 如果\(b<0\),因为有\(a>0\)了,可以知道\(i\leq d=\lceil\frac{-b}{a}\rceil\)时都会有\(\lfloor\frac{ai+b}{c}\rfloor<0\)。消掉前面这部分,\(F(n,a,b,c)=F(n-d,a,b+ad,c)\)
\(a,b\)转正之后\(\max\)操作没有用了,问题变成\(\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\)
如果\(a\geq c\)或\(b\geq c\),设\(a'=\lfloor\frac ac\rfloor,b'=\lfloor\frac bc\rfloor,a_0=a\mod c,b_0=b\mod c\)。
\(\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor=\sum_{i=0}^n\lfloor\frac{(a'c+a_0)i+b'c+b_0}{c}\rfloor\)
\(=\sum_{i=0}^n\lfloor\frac{a_0i+b_0}{c}\rfloor+\sum_{i=0}^na'i+b'(n+1)\)
\(=F(n,a_0,b_0,c)+a'C_{n+1}^2+b'(n+1)\)
否则考虑一个平面上的直线\(f(x)=\lfloor\frac ac\rfloor x+\lfloor\frac bc\rfloor\)。那么求的是满足\(x\in [0,n],y>0\)而且在这条直线下方的整点数。
这些整点最大的\(y\)显然是\(m=\lfloor\frac{an+b}{c}\rfloor\)
考虑拆了式子,\(F(n,a,b,c)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\)
\(=\sum_{i=0}^n\sum_{j=1}^m[j\leq \frac{ai+b}{c}]\)
因为\(b<c\)所以\(i=0\)没有用,稍作变换:
\(=\sum_{i=1}^n\sum_{j=1}^m[cj\leq ai+b]\)
\(=\sum_{i=1}^n\sum_{j=1}^m[ai\geq cj-b]\)
\(=\sum_{j=0}^{m-1}\sum_{i=1}^n[ai\geq cj-b+c]\)
\(=\sum_{j=0}^{m-1}\sum_{i=1}^n[ai> cj-b+c-1]\)
\(=\sum_{j=0}^{m-1}n-\sum_{i=1}^n[ai\leq cj-b+c-1]\)
\(=nm-\sum_{j=0}^{m-1}\sum_{i=1}^n[i\leq \frac{cj-b+c-1}{a}]\)
\(=nm-\sum_{j=0}^{m-1}\lfloor\frac{cj-b+c-1}{a}\rfloor\)
\(=nm-F(m-1,c,c-b-1,a)\)
类似辗转相除法,这个过程是\(O(\log n)\)的。
https://codeforces.com/contest/1098/submission/56515109
最新文章
- Node.js与Express4安装与配置
- SQL SERVER安装提示“安装了 Microsoft Visual Studio 2008 的早期版本
- C语言指针类型 强制转换
- ps存jpeg,格式保存的时候为什么选择“基线”
- python2.7学习记录之四
- Commons Codec基本使用(转载)
- oo第二次博客作业
- GitHub项目功能理解
- Eclipse 搭建 Strust2开发环境
- Python day 02
- [BZOJ 2759] 一个动态树好题
- 用PHP打造一个高性能好用的网站
- chrome浏览器下载内容存放位置
- HTML5 canvas getImageData() 方法
- POJ 2155 Matrix(二维BIT)
- 【UOJ Round #3】
- Java实现的简单神经网络(基于Sigmoid激活函数)
- setSupportActionBar()方法报错
- SQLSERVER 数据类型int、bigint、smallint 和 tinyint范围
- jQuery源码分析--Event模块(1)
热门文章
- MOOC C++笔记(六):多态
- C# 练习题 有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?
- React 语法
- pandas-07 DataFrame修改index、columns名的方法
- 【开发工具】- 如何导出/导入Idea的配置文件
- hbase完整分布式集群搭建
- MySQL Percona Toolkit--pt-osc执行SQL命令
- Java开发环境之MongoDB
- oracle 11g goldengate搭建(一)
- springboot2.1.3使用mvn site遇到的坑及解决方案