HDU5869 Different GCD Subarray Query 离线查询/区间贡献

题目思路

首先，区间 g c d gcd gcd收敛到 1 1 1的时间是 log ⁡ \log log，那么用维护区间内不同数字的数目的思路解决。

• 预处理所有右端点的 g c d gcd gcd集合
• 枚举右端点，加入右端点 g c d gcd gcd集合的贡献；如果在加入某个 g c d gcd gcd值时发现之前出现过，那么就清掉之前的贡献，然后固定右端点区间查询即可。
• 区间维护随便用一个结构维护即可，树状数组、线段树都行

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
int a[N];

namespace SegTree{
    #define ls rt = L && r > 1, ans = 0;
        if(mid >= L) ans += query(lson, L, R);
        if(mid > r; ans[i] = 0;
        qr[r].emplace_back(query{l, i});
    }

    for(int i = 1; i