某道 GCD 题
给一个 $n\times m$ 矩阵，元素为 $1-n\times m$ 的排列，问你所有子矩阵的 GCD 之和。
反正我想的是考虑一个右下角，移动左上角来统计答案，这样的话考虑到 gcd 的变化次数是$\log$ 的，说不定有救，但是需要完成区间取 GCD，这个不好做。
想一下，这个做法没有利用到每个数只出现一次的性质，通常这种只出现一次的性质往往和倍数这些相联系，不妨换个思路考虑，考虑 $i$ 的倍数的子矩阵的数量，然后发现容斥一下就可以得到答案。统计 $i$ 的倍数的子矩阵数量不难。
NOI2021D1T1
我想了一下，链是会做的，树链剖分，就是把树变成 $\log$ 个链来做。
然后其实每条重链按照链的方式来做，重链的交汇处需要特殊处理。
不妨把边下放到点，发现如果一个点的父亲的修改时间晚于该点的修改时间，那么这个点所代表的链就没用，所以对每个点维护两个东西，一个是该点的修改时间，另一个是该点代表的边是否被修改成重边。
查询的时候对链的交界处需要查修改时间判断是否有效。
其实有个更简易的方式，就是把修改看成染色，一条边有贡献当且仅当其两个端点颜色相同，这个很容易用树剖维护。
这两种方式其实体现出处理边的两种方式——下放到点考虑，考虑两个端点的状态。
需要灵活运用这两种方式解题。