选拔赛

· · 个人记录

选拔赛

Description

给定 n 个整数 a_i，q 次询问，每次给定 l, r，求有多少个 [l, r] 中的整数 i 满足 a_i 是 a_k, \forall k \in [l, r] 的约数。

Analysis

当一个数 a_x(x \in [l, r]) 是 a_k, \forall k \in [l, r] 的约数时，那么就可以得到以下结论：

第一条很显然。对于第二条，因为 a_l, a_{l + 1}, \dots a_r 中是包含 a_x 的，所以它们的最大公约数必定 \le a_x。又因为 a_x 是所有数的公约数，所以可以等号可以取到，所以第二条结论是正确的。

那么对于一个区间的询问，只有在 \min\limits_{k = l}^r(a_k) = \gcd\limits_{k = l}^r (a_k) 时，这个区间的答案才不为 0。那么在等式成立时，计算有多少个符合条件的值，也就是求有多少个 a_x。

根据 a_x = \min\limits_{k = l}^r(a_k) 这个结论，也就是 a_x 是 [l, r] 中有的最小值。所以 a_x 的数量也就是 [l, r] 中最小值的数量。那么问题就解决了。

Algorithm

需要维护三个值：区间最大公约数，区间最小值，区间最小值的出现次数。

区间最大公约数和区间最小值可以 ST 表 \mathcal O(n \log n) 预处理 + \mathcal O(1) 查询。对于区间最小值的出现次数，可以利用前缀和的思想，预处理每个数字在原序列中的出现位置，询问时二分查找即可。

Code

#include <bits/stdc++.h>

using namespace std;

#define re          register
#define il          inline
#define fup(x, l, r) for (re int x = (l), eNd = (r); x <= eNd; ++ x )
#define fdw(x, r, l) for (re int x = (r), eNd = (l); x >= eNd; -- x )

#define int long long

const int N = 1e6 + 10; 

il int Max(int a, int b) { return a > b ? a : b; }
il int Min(int a, int b) { return a < b ? a : b; }
il int read() { re int x = 0; re bool f = true; re char c = getchar(); while (c < 48 || c > 57) { if (c == '-') f = false; c = getchar(); } while (c >= 48 && c <= 57) x = (x << 3) + (x << 1) + c - 48, c = getchar(); return f ? x : -x; }
il void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + 48); }
il void wel(int x) { write(x), putchar('\n'); }
il void wsp(int x) { write(x), putchar(' '); }

int n, q, a[N], l, r;
int stmn[N][20], stgcd[N][20];
vector<int> v[N];
int res;

void init()
{
    fup (i, 1, n)
        stmn[i][0] = stgcd[i][0] = a[i];

    fup (j, 1, 19)
        fup (i, 1, n - (1 << j - 1))
        {
            stgcd[i][j] = __gcd(stgcd[i][j - 1], stgcd[i + (1 << j - 1)][j - 1]);
            stmn [i][j] =   min(stmn [i][j - 1], stmn [i + (1 << j - 1)][j - 1]);
        }
}

int querygcd(int l, int r)
{
    int k = log2(r - l + 1);
    return __gcd(stgcd[l][k], stgcd[r - (1 << k) + 1][k]);
}

int querymn(int l, int r)
{
    int k = log2(r - l + 1);
    return min(stmn[l][k], stmn[r - (1 << k) + 1][k]);
}

int cnt(int x, int k)       // 在 [1, k] 中出现了几个 x 
{
    if (v[x].empty()) return 0;
    int l = 0, r = v[x].size() - 1, res = 0;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (v[x][mid] == k) return mid + 1;
        if (v[x][mid] < k) l = mid + 1, res = mid + 1;
        else r = mid - 1;
    }
    return res;
}

signed main()
{
    freopen("pk.in", "r", stdin);
    freopen("pk.out", "w", stdout);

    n = read(), q = read();

    fup (i, 1, n)
        a[i] = read(),
        v[a[i]].push_back(i);

    init();

    while (q -- )
    {
        l = read(), r = read();
        int d = querygcd(l, r);
        int mn = querymn(l, r);

        res = r - l + 1;
        if (d == mn) res = r - l + 1 - cnt(mn, r) + cnt(mn, l - 1);
        wel(res);
    }

  return 0;
}