【20181102T1】优美的序列【二分+ST表】

题面

【正解】

相当于是

(GCD_{i=L}^{R} A_i = min_{i=L}^{R} {A_i})

然后GCD可以用ST表实现(O(log A_i))查询

并且GCD是递减的，所以枚举每个数，左、右依次二分使区间GCD等于这个数

复杂度(O(NlogN(logN+logA_i)))

代码