Codeforces Round #705 (Div. 2)

链接：https://codeforces.com/contest/1493

D ：GCD of an Array

题意：

给定一个长度为 \(n\) 的序列，\(q\) 次操作： 每次操作将 \(a_x\) 乘上 \(d\) 。每次操作完后询问全部数字的 \(gcd\)。

思路：

我们考虑使用线段树。对于每个节点，我们很容易想到维护其区间的 \(gcd\) 。但这其实是行不通的， 因为我们有至多 \(2e5\) 次操作， 每次最大又是乘上 \(2e5\)。显然会爆LL。但是我们可以分解质因数，以这样的形式储存信息，在上传到根节点时，将其再乘回原数， 输出即可。
所以我们对叶子节点，存储其对应数的分解质因数以后的形式。使用一个 \(map\) 来存储。 那么很显然，父亲存储的是两个儿子的 \(gcd\)， 在分解质因数的形式下， 也就是左右儿子的共同拥有的质因数, 且每个数取其中的最小值。那么我们就完成了建树。
我们考虑更新，只需要递归到叶子节点将其维护的信息修改即可。在上传信息时，只需要按建树时的逻辑，维护其父节点的信息即可。 但是此处我们一个优化 ：
显然我们在叶子节点更新信息时，只需要将乘上的数的分解质因子形式。也就是说，在原来的 \(map\) 中只有该数的质因子会被修改。那么在上传的时候同理， 并且由于另一个儿子和 \(gcd\) 的约束， 受到更新的信息只会越来越少，我们完全没有必要遍历每个节点的 \(map\)。为了完成此，我们需要在节点中多维护一个 \(vector\) 代表这次上传信息时，该节点哪些信息被修改了。
最后我们考虑查询。这显然是一件很简单的事情，只需要遍历根节点的 \(map\) 将其质因子形式乘回原数即可。 但如果这样我们会发现仍然得到了 \(TLE\) 的答案。 仔细思考我们便会发现， 这与之前向上更新信息的道理是一样的。 我们每一次查询是否需要重新遍历整个 \(map\) 呢？其实很显然我们每一次修改以后根节点的 \(map\) 中只会有很少的信息被改变了。 所以我们可以在全局开一个 \(map\) 来记录一次修改以后 根节点的各质因数的增加情况。每一次的查询只需要在上一次答案的基础上增加新的信息即可。
还有要注意的是:

1. 我们可以事先预处理出所有数的分解后的形式，存储在一个 \(vector\) 数组中，多次使用只需要直接调用即可。
2. 第一次查询我们需要遍历根节点信息。
3. 注意清空使用后的节点的 \(vector\)。
   总时间复杂度\(O(不大好算，自己算)\)

代码：

#include<bits/stdc++.h>using namespace std;#define endl '\n'#define all(a) a.begin(),a.end()#define pii pair<int, int>#define iloveds std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)typedef long long ll;const int N = 2e5 + 10;const ll mod = 1e9 + 7;int n, q;bool f = 0;ll last;vector<int> g[N];ll qpow(ll a, ll n){    ll ans = 1;    while(n){        if(n & 1){            ans = (ans * a) % mod ;        }        a = (a * a) % mod ;        n >>= 1;    }    return ans % mod;}int prime[N]; int v[N];int cnt;void get_prime(int n) {    for(int i = 2;i <= n; ++i){        if(v[i] == 0){            v[i] = i;            prime[++cnt] = i;        }        for(int j = 1 ; j <= cnt;++j){            if(prime[j] > v[i] || i * prime[j] > n) break;            v[prime[j] * i] = prime[j];        }    }}void divide(int n) {    int nn = n;    while (v[n]) {        g[nn].push_back(v[n]);         n /= v[n];    }}int a[N];map<int,int> add;struct node{    map<int,int> mp;    vector<int> vis;}seg[N << 2];void pushup(int id){    for(auto i : seg[id << 1].mp){        if(seg[id << 1 | 1].mp.count(i.first)){            seg[id].mp[i.first] = min(seg[id << 1].mp[i.first], seg[id << 1 | 1].mp[i.first]);        }    }}void pushup1(int id){    if(seg[id << 1].vis.size() != 0){        for(auto i : seg[id << 1].vis){            int tmp = seg[id].mp[i];            seg[id].mp[i] = min(seg[id << 1].mp[i], seg[id << 1 | 1].mp[i]);            if(tmp != seg[id].mp[i]) {                seg[id].vis.push_back(i);                if(id == 1) add[i] = seg[id].mp[i] - tmp;             }        }        seg[id << 1].vis.clear();    }    if(seg[id << 1 | 1].vis.size() != 0){        for(auto i : seg[id << 1 | 1].vis){            int tmp = seg[id].mp[i];            seg[id].mp[i] = min(seg[id << 1].mp[i], seg[id << 1 | 1].mp[i]);            if(tmp != seg[id].mp[i]) {                seg[id].vis.push_back(i);                if(id == 1) add[i] = seg[id].mp[i] - tmp;             }                    }        seg[id << 1 | 1].vis.clear();    }}void build(int id, int l, int r){    if(l == r){        for(auto i : g[a[l]]){            seg[id].mp[i] ++;        }    }else{        int mid = (l + r) >> 1;        build(id << 1, l, mid);        build(id << 1 | 1, mid + 1, r);        pushup(id);    }}void change(int id, int l, int r, int pos, int val){    if(l == r){        for(auto i : g[val]){            seg[id].mp[i] ++;            seg[id].vis.emplace_back(i);        }    }else{        int mid = (l + r) >> 1;        if(pos <= mid){            change(id << 1, l, mid, pos, val);        }else{            change(id << 1 | 1, mid + 1, r, pos, val);        }        pushup1(id);    }}ll query(ll last){    ll tmp = 1;    if(!f){        for(auto i : seg[1].mp){            tmp *= qpow(i.first, i.second);            tmp %= mod;        }        f = 1;        last = tmp % mod;        add.clear();        return tmp % mod;    }    ll ans = last;    for(auto i : add){        ans *= qpow(i.first, i.second);        ans %= mod;    }    add.clear();    return ans % mod;}int main(){    iloveds;    get_prime(N - 10);    for(int i = 2; i <= N - 10; i ++) divide(i);    cin >> n >> q;    for(int i = 1; i <= n ; i ++) {        cin >> a[i];    }    build(1, 1, n);    last = 1 ;    while(q --){        int x, d;        cin >> x >> d;        if(n == 1){            cout << (last * d) % mod << endl;            last = (last * d) % mod;            continue;        }        change(1, 1, n, x, d);        last = query(last);        cout << last << endl;    }    return 0;}