顶级智斗，CodeChef GCD Subsequences
题目是 https://vjudge.net/problem/CodeChef-GCDS ，我从
直接截取我和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
流泪的小酒窝: 哦你说的好像是对的
我靠
逆天
但是斜率优化不行，这里是
其中