D. GCD of an Array

https://codeforces.com/problemset/problem/1493/D
题意：给定一个序列，有q次询问，每次将其中一个数×上ki，问每次操作后全体gcd为多少。
n,q<=2e5.
题解：这题思路很一眼，无非是维护每一个数的素因数以及其指数，存每个数中素因数出现的次数，每次操作判断改变后的素因数集合中最小元素。问题主要是实现，具体而言我们可以用map[i]维护每一个数的素因数出现次数，用mutiset[p]维护素数p在各个a[i]中出现的次数，若没出现则不放入，每次求最小元素即可，单次询问复杂度为log*log。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int const maxn = 2e5 + 5, max_val = 2e5 + 5;
ll mod = 1e9 + 7, ans = 1;
int nxt[max_val], n;
multiset <int> cnt[max_val];
map <int, int> cnt_divisor[maxn];

void add(int i, int x) {
    while (x != 1) {
        int div = nxt[x], add = 0;
        while (nxt[x] == div) add++, x = x / nxt[x];

        int lst = cnt_divisor[i][div];
        cnt_divisor[i][div] += add;
        int lst_min = 0;
        if ((int)cnt[div].size() == n) {
            lst_min = (*cnt[div].begin());
        }
        if (lst != 0) {
            cnt[div].erase(cnt[div].find(lst));
        }
        cnt[div].insert(lst + add);
        if ((int)cnt[div].size() == n) {
            for (int j = lst_min + 1; j <= (*cnt[div].begin()); ++j) {
                ans = ans * (ll)div % mod;
            }
        }
    }
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int q, l, x;
    cin >> n >> q;

    for (int i = 2; i < maxn; ++i) {
        if (nxt[i] == 0) {
            nxt[i] = i;
            if (i > 10000) continue;
            for (int j = i * i; j < maxn; j += i) {
                if (nxt[j] == 0) nxt[j] = i;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cin >> x;
        add(i, x);
    }

    for (int i = 1; i <= q; ++i) {
        cin >> l >> x;
        add(l, x);
        cout << ans << '\n';
    }

    return 0;
}

B. BinCoin 哈希

https://codeforces.com/problemset/problem/1773/B
题意：给定n个点，组成一棵二叉树，给出k个排列，每个表示对这个二叉树的一种遍历，具体而言，从根节点开始，若该点无子节点，则记录后传给父节点，否则随机选择一个儿子下发，再次传上时记录。还原该树。
n<=1000,50<=k<=100
题解：这题的性质也比较好观察，即对一颗子树，其根节点左右两侧元素集合总是那两个集合，那么我们可以每次找到根后拆分问题求解，但直接做复杂度为nnnk，问题在于对集合的处理。我们对点做哈希，hash[i]=2^i%mod.再对于每个排列计算前缀和，这样我们的询问不需要nk，只需要k即可，最后总复杂度为nn*k.

E. Node Pairs

https://codeforces.com/problemset/problem/1763/E
题意：我们称有序对为u!=v&u->v可达但v->u不可达。我们定义p可达图为图中有p对点两两可互相到达，则现在给你一个数k，问需要构建一张图k可达，至少需要多少个点，同时，再满足最少点数情况下，最多有多少有序对。
k<=2e5
题解：观察发现，组成可达对的点是又一组组完全图组成的，换言之，我们即为求将k分解为若干个n(n-1)/2形式的数之和，问最小点数。我们可以dp求解，dp(i)表示k=i时，表示k所需的最小点数，f(i)=min(f(i),f(i-a(j))+j),a(j)表示为j个点形成的可达对数量，由于 a[j]=j(j-1)/2,故复杂度为n*sqrt(n).
而对于如何最大化有序对，即可转化为现有w个点，每个点有一个权值，u->v使得答案增加二者之积，且图为有向无环图。我们可以贪心地得到答案，我们每次取集合中最大的数，将其与所有剩下的数连边，这样结果必定最大且不存在环，证明很显然，留给读者。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
int a[N],b[N],f[N],pre[N],s[N];
signed main(){
	int n;cin>>n;
	for(int i=2;i<=10000;i++){
		a[i]=(i-1)*i/2;
	}
	for(int i=1;i<=n;i++) f[i]=1e18;
	for(int i=1;i<=n;i++){
		for(int j=2;;j++){
			if(a[j]>i) break;
			if(f[i]>f[i-a[j]]+j) pre[i]=j;
			f[i]=min(f[i],f[i-a[j]]+j);
		}
	}
	int x=n,t=0;
	while(x){
		int w=pre[x];
		b[++t]=w;
		x-=a[w];
	}
	cout<<f[n]<<" ";
	sort(b+1,b+t+1);
	for(int i=1;i<=t;i++){
		s[i]=s[i-1]+b[i];
	}
	int ans=0;
	for(int i=t;i>=1;i--){
		ans+=b[i]*(s[i-1]);
	}
	cout<<ans;
}

E. A-Z Graph

https://codeforces.com/contest/1494/problem/E
题意：给定一个包含 n 个顶点的有向图。每个有向边（或弧）都标有一个字符。初始时，图为空。
你需要处理 m 个查询。每个查询有三种类型之一：1，u，v