顶级智斗，CodeChef GCD Subsequences

题目是 https://vjudge.net/problem/CodeChef-GCDS ，我从$O(n2^{\omega(v)}\omega(v))$优化到了$O(n\left(\frac{\log v}{\log\log v}\right)^3)$，或者说$O(n(\omega(v))^3)$，从亚指数到多项式了

直接截取我和1姐聊天记录，本来是和zcz在讨论，讨论了好多（虽然我水平不高，之前想到的东西一直是zcz的子集），但是我给出这个做法的时候他在写题，懒得理我，只好去找1姐，反正一个人会了整个机房就都会了

首先每个素数只需要保留一个

然后我枚举改的是i

最大化包含i的合法区间个数，那么往左往右找到，每个素数连续存在了多长

这样每个素数可以表示成[左边连到哪, 右边连到哪]这么一个区间

然后我们画到平面上

每个区间对应于点(i到左端点距离, i到右端点距离)

然后问题相当于，我选择若干个区间，选择一个可以获得这个点左下方2-side矩形内的所有点（每个点只能获得一次），并付出一个素数的代价，要求所有代价乘积<=5e5

最大化获得的点数

流泪的小酒窝: 2-side矩形是？

一个点为原点的矩形？

Chraenioumy!: 就是左下方

(x_0,y_0)的左下2-side矩形就是x<=x_0且y<=y_0的点集

好的那你现在理解这个转化了

流泪的小酒窝: 我理解了吗

Chraenioumy!: 你没理解吗

就是你一个素数对应一个点(x,y)的意思是，如果你让a_i改成的数包含这个素数，那么可以获得[i-x,i+y]这个区间的所有子区间

流泪的小酒窝: 就是每次取左下，总权重为左下面积并？

笛卡尔坐标系下

Chraenioumy!: 对的

然后你发现一个问题

我不会选两个点，一个在另一个左下方

然后我看所有x=0的点，所有y=0的点

它们分别是a_{i-1}不含的素数，和a_{i+1}不含的素数

那么我发现一个问题

设x=0的点乘积是p，y=0的点乘积是q

剩下的的乘积，设为g，一定是gcd(a_{i-1},a{i+1})的因数

而且pg<=v，qg<=v

也就是说我选整个pg，整个qg，都不会爆

那我考虑选pqg会发生什么

比如说，选pqg比选pg，答案多了k

意味着q里面的至少一个素数往右连续出现k次

并且i是这一段连续出现的左端点或者左端点-1

那么我们知道，对于所有i，选pqg比选pg，答案一共多了不超过n log v/loglog v

因为你所有素数一共出现这么多次

好的，那么我们就希望维度交换

流泪的小酒窝: 别急

这是怎么算出来的

Chraenioumy!: 因为你答案多了k，是因为这是某个素数连续出现k次的一段，的左端点或者左端点-1

是所有i的答案增量的和

不是一个i

如果你不考虑所有i的和，这个东西很难做

因为所有素数一共出现n log v/loglog v次

而每次出现让一个连续段长度增加1

而你的k的和

不超过连续段总长度

连续段的意思是，二元组(素数, 极长出现区间)的两倍

好的现在，如果答案多了k，但是爆了5e5的上界，我们希望少选一些，但是答案不能减少超过k

现在维度交换

dp(i,j)表示考虑到前i个点，第i个点选了，答案比全选少了j，最小的选的素数乘积是多少

转移枚举选的上一个点

点是按x从小到大排序的

这里"答案比全选少了多少"也是一步一步计算的

就是一边扫x一边计算

复杂度n(log v/loglog v)^3

流泪的小酒窝: 诶为啥是三方

Chraenioumy!: j总量n log v/loglog v

对于每个j，有log/loglog个i，转移枚举上一个i，也是log/loglog

指导意见: 优化到(log/loglog)^2

好像就是斜率优化就行了

指导意见: n1e6 v1e7投ur

流泪的小酒窝: 哦你说的好像是对的

我靠

逆天

但是斜率优化不行，这里是

其中$w(i,j)=s_j-s_i-(x_j-x_i)y_j$满足四边形不等式，$s$是全选情况下的前缀贡献。