P10403 题解

前言

怎么全是神秘二分？双指针不好吗？
传送门

思路

容易想到维护区间 $\gcd$ 使用 st 表，$O(n\log^2_n)$ 预处理，$O(n\log_n)$ 查询。
直接暴力查询每个区间 $O(n^2\log_n)$ 过不了一点。
看见了有人使用二分，但是考虑直接双指针。
单独考虑 $\gcd=2$ 和 $\gcd=3$ 的情况。观察到固定右端点的话，区间 $\gcd$ 随左端点单调递增（固定左端点的话，区间 $\gcd$ 随右端点单调递减）。
那么，固定右端点时，使得 $\gcd=2$ 的左端点也是一段区间。当我们右移右端点时，这段合法区间也要跟着右移（$\gcd=3$ 同理）。
那么直接双指针即可。注意判断合法情况，统计答案时也注意区间长度奇偶问题。
时间复杂度 $O(n\log^2_n)$，空间复杂度 $O(n\log_n)$。

Code

Talk is cheap, show me the code.

Code

// Problem: P10403 「XSOI-R1」跳跃游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10403
// Memory Limit: 128 MB
// Time Limit: 750000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace FastIO {
    char gc() {
        static char buf[1 << 24], *is = buf, *it = buf;
        if (is == it) is = buf, it = is + fread(buf, 1, 1 << 24, stdin);
        return is == it ? EOF : *is ++;
    }
    char out[1 << 24];
    int len;
    void flush() {fwrite(out, 1, len, stdout), len = 0;}
    void pc(char x) {if (len == 1 << 24) flush(); out[len ++] = x;}
    struct Flusher {~Flusher() {flush();} } Fls;
    // #define gc() getchar()
    // #define pc(X) putchar(X)
    inline void read(char& ch) {ch = gc();}
    inline void read(char *s) {
        char ch = gc();
        while (ch < 33 || ch > 126) ch = gc();
        for (; ch >= 33 && ch <= 126; ch = gc()) *s++ = ch;
        *s = '\0';
    }
    template <class T>
    inline void read(T &x) {
        char c, flag = 0;
        while ((c = gc()) < '0' || c > '9') flag |= c == '-';
        x = c & 15;
        while ((c = gc()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c & 15);
        if (flag) x = ~x + 1;
    }
    template <class T, class ...T1>
    inline void read(T &x, T1 &...x1) {read(x), read(x1...);}
    template <class T>
    inline void _put(T x) {if(x > 9) _put(x / 10); pc((x % 10) | 48);}
    template <class T>
    inline void write(T x) {if(x < 0) pc('-'), x = ~x + 1; _put(x);}
    template <> inline void write(char x) {pc(x);}
    template <class T, class ...T1>
    inline void write(T x, T1 ...x1) {write(x), write(x1...);}
}
using FastIO::read;
using FastIO::write;
template <class T>
inline bool chkmin(T &x, T y) {return x > y ? x = y, 1 : 0;}
template <class T>
inline bool chkmax(T &x, T y) {return x < y ? x = y, 1 : 0;}

const int N = 6e5 + 10, K = 20;
int n, a[N], st[N][K], lg[N], ans;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int query(int l, int r) {
    int k = lg[r - l + 1]; return gcd(st[l][k], st[r - (1 << k) + 1][k]);
}
int f2(int x) {x /= 2; return (x + 1) * x;}
int f3(int x) {return (x + (x % 2 ? 1 : 0)) * ((x + 1) / 2) / 2;}

signed main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    read(n), lg[0] = -1;
    for(int i = 1; i <= n; ++i)
        read(a[i]), st[i][0] = a[i], lg[i] = lg[i >> 1] + 1;
    for(int k = 1; k <= lg[n]; ++k) for(int i = 1; i + (1 << k) - 1 <= n; ++i)
        st[i][k] = gcd(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
    for(int i = 1, l = 1, r = 1; i <= n; ++i) {
        if(a[i] & 1) l = i + 1, r = i;
        else {
            while(r < i && query(r + 1, i) <= 2) ++r;
            while(l <= r && query(l, i) < 2) ++l;
            if(r >= l && query(r, i) == 2 && query(l, i) == 2)
                ans += f2(i - l + 1) - f2(i - r); 
        }
    }
    for(int i = 1, l = 1, r = 1; i <= n; ++i) {
        if(a[i] % 3) l = i + 1, r = i;
        else {
            while(r < i && query(r + 1, i) <= 3) ++r;
            while(l <= r && query(l, i) < 3) ++l;
            if(r >= l && query(r, i) == 3 && query(l, i) == 3)
                ans += f3(i - l + 1) - f3(i - r); 
        }
    }
    write(ans);
    return 0;
}

End

实际上本题时间瓶颈在于 st 表，使用二分与使用双指针并无太明显的差距，不过能写更优就是了（实际上还是慢的一批）。如有问题，欢迎指正。