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

题目思路

首先，区间收敛到的时间是，那么用维护区间内不同数字的数目的思路解决。

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

#include <bits/stdc++.h>
#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 << 1
    #define rs rt << 1 | 1
    #define lson ls, l,
    #define rson rs, mid + 1,

    int tree[N << 2];

    inline void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }

    void clear(int rt, int l, int r){
        tree[rt] = 0;
        if(l == r) return;
        int mid = l + r >> 1;
        clear(lson), clear(rson);
    }

    void update(int rt, int l, int r, int pos, int val){
        if(l == r) return (void)(tree[rt] += val);
        int mid = l + r >> 1;
        if(mid >= pos) update(lson, pos, val);
        else update(rson, pos, val);
        push_up(rt);
    }

    int query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tree[rt];
        int mid = l + r >> 1, ans = 0;
        if(mid >= L) ans += query(lson, L, R);
        if(mid < R) ans += query(rson, L, R);
        return ans;
    }
}

struct query{ int l, id; };

#define PII pair<int, int>
#define fir first
#define sec second
#define mkp make_pair

vector<query> qr[N];
vector<PII> v[N];

int ans[N];

#define SEGRG 1, 1,

inline void solve(int n, int q){
    SegTree::clear(SEGRG);
    for(int i = 1; i <= n + 5; i++) v[i].clear();
    for(int i = 1; i <= n + 5; i++) qr[i].clear();
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= q; i++){
        int l, r; cin >> l >> r; ans[i] = 0;
        qr[r].emplace_back(query{l, i});
    }

    for(int i = 1; i <= n; i++){
        v[i].emplace_back(mkp(a[i], i));
        int last_gcd = a[i];
        for(auto &pre : v[i - 1]){
            int val = pre.fir, ind = pre.sec;
            int now_gcd = __gcd(a[i], val);
            if(last_gcd != now_gcd) v[i].emplace_back(mkp(now_gcd, ind));
            last_gcd = now_gcd;
        }
    }
    unordered_map<int, int> last;
    for(int i = 1; i <= n; i++){
        for(auto &now : v[i]){
            SegTree::update(SEGRG, now.sec, 1);
            if(last.count(now.fir)) SegTree::update(SEGRG, last[now.fir], -1);
            last[now.fir] = now.sec;
        }
        for(auto &que : qr[i]){
            ans[que.id] = SegTree::query(SEGRG, que.l, i);
        }
    }

    for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

#undef SEGRG

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int n, q;
    while(cin >> n >> q) solve(n, q);
    return 0;
}