【HDU-5869】Different GCD Subarray Query

【HDU – 5869】Different GCD Subarray Query

【2016 ACM/ICPC Asia Regional Dalian Online】

【gcd+离线查询+树状数组】

问题链接:https://vjudge.net/problem/HDU-5869

Solution:

对于单次查询的暴力复杂度\(O(n^2)\),q次查询\(O(qn^2)\)显然不行,所以我们用下面这种策略:

考虑一下这个问题,如果对于一个固定的右端点(假设右端点5),

我们可以找到这个区间中所有不同gcd值的最右最小区间(原因在后面解释),

如果开一个数组,以左端点为下标,存储上图中以下标为左端点的区间的个数,则可以得到数组arr:

接下来,以输入样例中的查询”3 5″,只要算出上面arr[5] – arr[3 -1],也就是从下标从3到5的和,就可以得到答案。

因为我们一直选取的是最右区间,所以可以将每个同gcd值的最右最小区间种类数存放到左端点那里,这个问题就转化成对于一个数组区间求和问题,从直观上理解,只要一次查询包含这个最小最右区间,它就一定有该种gcd值。

对于求和,我们显然可以使用树状数组来优化这一过程,即使用左端点下标作为树状数组的下标,而上图的计数作为树状数组维护的值。

注意,上边我们所做的讨论一直是以右端点固定在5为前提的,到目前为止,我们解决了对于单个固定右端点时这个问题的解,当前这个问题则可以理解成它的“升级版”,多个右端点时这个问题的解。

我们显然可以由上一个右端点的所有最右区间推知下一个右端点的所有最小最右区间。于是我们可以开一个vector数组,将第i个右端点的最右区间放到这个数组的i号vector中,之后将多次询问按照右端点排序,接着一边从左到右维护树状数组,一边查询以当前遍历到的点为右端点的所有查询,最后按照输入的顺序输出,这个问题就可以得到解决。

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
// #define DBG
using namespace std;

const int LIM = 1e5 + 10;
const int MAXI = 1e6 + 10;
struct query {
    int l, r, idx;
    bool operator < (const query & q) const {
        return r < q.r;
    }
} qs[LIM];
int data[LIM];
int bit[LIM];
int vis[MAXI];
int ans[LIM];
int n;
vector<pair<int, int> > gcds[LIM];

inline int gcd(int a, int b) {
    return a % b ? (gcd(b, a % b)) : b;
}

inline int lowbit(int x) {
    return x & (-x);
}

void add(int pos, int diff) {
    while (pos < n) {
        bit[pos] += diff;
        pos += lowbit(pos);
    }
}

int getSum(int pos) {
    int ret = 0;
    while (pos) {
        ret += bit[pos];
        pos -= lowbit(pos);
    }
    return ret;
}

int main(void) {
    int q;
    while (~scanf("%d%d", &n, &q)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", data + i);
            gcds[i].clear();
        }
        /* discretization */
        for (int i = 1; i <= n; i++) {
            int g = data[i], lp = i;
            for (int j = 0; j < gcds[i - 1].size(); j++) {
                int tmpg = gcd(g, gcds[i - 1][j].first);
                if (g != tmpg) {
                    gcds[i].push_back(make_pair(g, lp));
#ifdef DBG
                    printf("[%d] : (%d, %d)\n", i, g, lp);
#endif
                    g = tmpg;
                    lp = gcds[i - 1][j].second;
                }
            }
            gcds[i].push_back(make_pair(g, lp));
#ifdef DBG
            printf("[%d] : (%d, %d)\n", i, g, lp);
#endif
        }
        /* input the query and sort them */
        for (int i = 0; i < q; i++) {

            scanf("%d%d", &qs[i].l, &qs[i].r);
            qs[i].idx = i;
        }
        sort(qs, qs + q);
        /* operation of the binary index tree */
        memset(vis, 0, sizeof vis);
        memset(bit, 0, sizeof bit);
        int pos = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < gcds[i].size(); j++) {
                int g = gcds[i][j].first;
                int lp = gcds[i][j].second;
                if (vis[g]) add(vis[g], -1);
                add(lp, 1);
                vis[g] = lp;
            }
            while (qs[pos].r == i) {
                ans[qs[pos].idx] = getSum(qs[pos].r) - getSum(qs[pos].l - 1);
                pos++;
            }
#ifdef DBG
            printf("-----------------\n");
            for (int i = 1; i <= 5; i++)
                printf("%d: %d\n", i, bit[i]);
#endif
        }
        for (int i = 0; i < q; i++) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}