牛客2018提高组模拟day4 T2 区间 差分

我的做法似乎和泥萌不太一样啊。。还常数挺大 不过也是$O(n)$O(n)的

• 记$f[i]$f[i]表示$i$i作为GCD的时候能向左拓展的格数
• 可以发现如果能拓展 f[i] = f[i + 1] + 1 直到拓展到一个不能整除的格子
• 上面的式子是可以在数组上差分来算的。
• 设cur为当前gcd的下标 那么每次拓展之后 f[i]++， f[cur-1]–;
• 反向同理 倒过来做一遍就行
• 最后加一下 取最大值 就是答案了

最后一个点被猫卡了读入 我的快读不够快 用了cuking的快读板子就AC了==
附上我的代码和cuking的板子链接
板子

---

UPD:加了register 卡常过了

Code(100pts)

#include<cstdio>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
#define maxn 4000007
#define maxm 1000001
#define V e[i].v
#define ull unsigned long long
#define R register
int n, m, k, tot;
inline ll read(){
    R ll s = 0, f = 1; R char c = getchar();
    while (c > '9' || c < '0') {if(c=='-') f= -1; c = getchar();}
    while (c >= '0' && c <= '9') {s = s * 10 + c - '0'; c = getchar();}
    return s * f;
}
ll f[maxn], g[maxn], a[maxn], cur, ans;
int main(){
    n = read();
    for (R int i = 1; i <= n; i++) a[i] = read();
    cur = 1;
    for (R int i = 1; i <= n; i++) {
        if (a[i] % a[cur] == 0) {  //min仍为gcd
            f[i]++; f[cur - 1]--;
        } else {
            cur = i;
            f[i]++;
            f[cur - 1]--;
        }
    }
    cur = n;
    for (R int i = n; i >= 1; i--) {
        if (a[i] % a[cur] == 0) {
            g[i]++;
            g[cur + 1]--;
        } else {
            cur = i;
            g[i]++;
            g[cur + 1]--;
        }
    }
    for (R int i = 1; i <= n; i++) g[i] += g[i - 1];
    for (R int i = n; i >= 1; i--) f[i] += f[i + 1], ans = Max(ans, f[i] + g[i] - 1);
    printf("%lld\n", ans);
    return 0;
}