HDU7107. GCD on Sequence

题意：

见原题。

分析：

这是一个计数问题。

我们很容易想到一个暴力解法，那就是直接暴力统计，复杂度为\(O(n^3)\)，想法是枚举每一个区间，然后暴力计算每个区间的值，顺带统计。

我们除了枚举区间之外，还能枚举\(v\)，然后统计有多少个区间的值等于这个\(v\)。暴力的统计直接变成\(O(n^4)\)，虽然复杂度更劣，但是这种枚举方式留给了我们优化的空间。

首先，由于\(v\)是最大值，故而枚举\(v\)的顺序应是从大到小。枚举\(v\)的顺序从大到小有什么好处呢？当\(v\)枚举到\(v_0\)时，若此时一个区间\([l,r]\)上存在\(i,j\)使得\(\gcd(i,j)=v_0\)，且之前枚举比\(v_0\)大的数时这个区间\([l,r]\)上的这个条件都不成立，那么\([l,r]\)上的值就是\(v_0\)。想到这，头脑中大概会浮现出一种抽象的数据结构，维护当前枚举到\(v_0\)时，哪些区间的答案已经确定下来（先想象有一种魔法可以快速维护）。可以想见，一开始所有区间的值都还没确定，每一步都会有若干的区间的值被确定下来，然后我们只要统计每一步确定下来的区间个数就可以了。但是想到这，复杂度远远不够，但是这起码给进一步优化提供了思路。

我们发现，如果一个区间的值是\(v\)，那么该区间内至少有\(2\)个数是\(v\)的倍数（换言之，这是必要条件）。这个发现告诉我们，对于一个特定的\(v_0\)，可能不需要枚举\(O(n^2)\)这么多次，而是只需要考虑\(v_0\)的倍数。也许你会说，有两个数是\(v_0\)的倍数，这个区间的值不一定是\(v_0\)。但是我说，至少这个区间的值是大于等于\(v_0\)的（想想为什么）。那么再想一下上面\(v\)从大到小的枚举方式，发现这两者是非常契合的。考虑\(v\)的倍数，复杂度是远远小于\(O(n^2)\)的。为了接下来方便描述，我们设\(g_i\)为\(i\)的所有小于等于\(n\)的倍数在\(a\)中的位置，\(g_i(j)\)为\(i\)的倍数第\(j\)次出现在\(a\)中的位置。

现在问题的主要矛盾转向了那个抽象的数据结构该怎么实现。要维护区间，区间个数的范围可太大了，不现实。这时，我们又发现，给定一个左端点\(l\)，随着右端点\(r\)从小到大，区间\([l,r]\)上的值是单调不减的。这个发现告诉我们，当\(v\)按照上述方式枚举到特定值\(v_0\)时，此时，如果存在一个区间\([l,r_0](l\leq r_0\leq r)\)它的值是已经确定的，那么对于所有满足\(r>r_0\)的区间\([l,r]\)的值都是已经确定了的。反之，如果存在一个区间\([l,r_0](l\leq r_0\leq r)\)它的值目前还没确定，那么对于所有满足\(r<r_0\)的区间\([l,r]\)的值都是还没确定的。所以，对于给定的\(l\)，我们可以维护满足区间\([l,r_0]\)是不确定的最大的\(r_0\)。这样维护的东西就少了很多。

接下来，考虑怎么维护，以及怎么在维护的同时统计答案。由于上面的单调性，我们只需要考虑在\(a\)中相邻的\(i\)的倍数，即\(g_i(j)\)和\(g_{i}(j+1)\)，那么这一步我们可以肯定所有满足\(l\leq g_i(j)\)且\(r\geq g_i(j+1)\)的区间\([l,r]\)都是被确定的，也就是说对于维护的序列，区间\([1,g_i(j)]\)上的值都应“至少”被更新到\(g_i(j+1)-1\)（这里“至少”的含义为，对于区间\([1,g_i(j)]\)上的某一点，如果之前的值是小于等于\(g_i(j+1)-1\)，那就不必再更新了，只有之前的值是大于\(g_i(j+1)-1\)的，才需要更新）。为了在维护的同时统计答案，我们要统计，这里面有哪些区间是这一步才被确定的。当然是必须要在这一步被更新的点所对应的区间是这一步才被确定的。那么数量是多少呢？根据前面的说法，对于维护的序列来说，肯定越更新越小，假如某一点从\(x\)更新到了\(y\)，说明，这一点上有\(x-y\)个区间被新确定了。对于没更新的那些点，我们可以认为它从\(x\)更新到了\(x\)，有\(x-x\)个区间被新确定了。那么对于所有点的贡献加起来，就是原来的区间和减掉新的区间和。

经过上面的分析，我们发现这个数据结构需要用线段树实现。对于维护的序列来说，区间更新的操作相当于是\([1,g_i(j)]\)区间上的数和\(g_i(j+1)-1\)取最小值。这个用通常的线段树实现起来比较麻烦（有一种奇妙的线段树叫Segment Tree Beats就可以做这样的事）。这里由于维护的序列比较特殊，既然之前说过，给定一个左端点\(l\)，随着右端点\(r\)从小到大，区间\([l,r]\)上的值是单调不减的，那么也应该能想到，随着\(l\)增大，所维护的满足区间\([l,r_0]\)是不确定的最大的\(r_0\)也是不减的（想想为什么）。那么所谓区间取最小值的操作，实际上可以通过线段树上的二分转化为另一个区间覆盖的操作。

最终的复杂度是\(O(n\log^2 n)\)。

代码：

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define now nodes[rt]
#define ls nodes[rt << 1]
#define rs nodes[rt << 1 | 1]
typedef long long Lint;
const int maxn = 1e5 + 10;
int n;
int a[maxn], pos[maxn];
struct Node {
    Lint sum;
    Lint r_val;
    Lint tag;
    int l, r;
};
struct Seg {
    Node nodes[maxn << 2];

    void update_node(int rt, Lint tag) {
        now.sum = tag * (now.r - now.l + 1);
        now.r_val = tag;
        now.tag = tag;
    }

    void pushup(int rt) {
        now.sum = ls.sum + rs.sum;
        now.r_val = rs.r_val;
    }

    void pushdown(int rt) {
        if (now.tag) {
            update_node(rt << 1, now.tag);
            update_node(rt << 1 | 1, now.tag);
            now.tag = 0;
        }
    }

    void build(int rt, int l, int r, Lint val) {
        now.l = l, now.r = r;
        now.tag = 0;
        if (l == r) {
            now.sum = val;
            now.r_val = val;
            return;
        }
        int mid = l + r >> 1;
        build(rt << 1, l, mid, val);
        build(rt << 1 | 1, mid + 1, r, val);
        pushup(rt);
    }

    // 用val覆盖区间[L, R]
    void update(int rt, int L, int R, Lint val) {
        if (L <= now.l && now.r <= R) {
            update_node(rt, val);
            return;
        }
        pushdown(rt);
        if (L <= ls.r)
            update(rt << 1, L, R, val);
        if (R >= rs.l)
            update(rt << 1 | 1, L, R, val);
        pushup(rt);
    }

    // 区间[1,n]的和
    Lint query_sum() { return nodes[1].sum; }

    // 寻找第一个大于val的位置
    int query_pos(int rt, Lint val) {
        if (now.l == now.r) {
            return now.l;
        }
        if (ls.r_val > val) {
            return query_pos(rt << 1, val);
        } else {
            return query_pos(rt << 1 | 1, val);
        }
    }
} seg;

// g[i]存<=n的i的倍数的位置
vector<int> g[maxn];

Lint ans[maxn];
void solve() {
    seg.build(1, 1, n, n);
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            g[i].push_back(pos[j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
    }
    // 从大到小枚举val
    for (int i = n; i >= 1; i--) {
        ans[i] = 0;
        for (int j = 0; j < g[i].size() - 1; j++) {
            Lint o_sum = seg.query_sum();
            if (seg.nodes[1].r_val > g[i][j + 1] - 1) {
                int pos = seg.query_pos(1, g[i][j + 1] - 1);
                if (pos <= g[i][j])
                    seg.update(1, pos, g[i][j], g[i][j + 1] - 1);
            }
            Lint n_sum = seg.query_sum();
            ans[i] += o_sum - n_sum;
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", ans[i]);
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            pos[a[i]] = i;
        }
        solve();
    }
    return 0;
}