Codeforces Round #705 (Div. 2)

给定一个长度为 \(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;
}