T1
分别对序列和值域分块。
只需要做到\(O(\sqrt{n})\)查询\(O(1)\)修改就可以了。
这样的话与处理一下序列和值域分块的情况。
查询的时候动态的处理散块就可以在\(O(\sqrt{n})\)复杂度维护\(K\)大值。
T2
直接推式子。
\[\begin{aligned} ans&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{K}f_k(gcd(i,j))\\ &=\sum\limits_{k=1}^{K}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}f_k(gcd(i,j))\\ &=\sum\limits_{k=1}^{K}\sum\limits_{d=1}^{n}f_k(d)\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{n}{d}}[gcd(i,j)=1]\\ &=\sum\limits_{k=1}^{K}\sum\limits_{d=1}^{n}f_k(d)\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{n}{d}}\sum\limits_{g|gcd(i,j)}\mu(g)\\ &=\sum\limits_{k=1}^{K}\sum\limits_{d=1}^{n}f_k(d)\sum\limits_{g=1}^{\frac{n}{d}}\mu(g)\lfloor\frac{n}{dg}\rfloor^2\\ &=\sum\limits_{k=1}^{K}\sum\limits_{T=1}^{n}\lfloor\frac{n}{T}\rfloor^2\sum\limits_{d|T}\mu(d)f_k(\frac{T}{d})\\ H_k(n)&=\sum\limits_{d|n}\mu(d)f_k(\frac{n}{d})\\ H_k&=\mu*f_k\\ H_k(p^e)&=\mu(p^0)f_k(p^e)+\mu(p^1)f_k(p^{e-1})\\ n=&\prod\limits_{i=1}^{w}p_i^{c_i}\\ g(n)&=\prod\limits_{i=1}^{n}(-1)^{c_i}\\ \end{aligned}\]
\[\begin{aligned} ans&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{K}f_k(gcd(i,j))\\ &=\sum\limits_{k=1}^{K}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}f_k(gcd(i,j))\\ &=\sum\limits_{k=1}^{K}\sum\limits_{d=1}^{n}f_k(d)\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{n}{d}}[gcd(i,j)=1]\\ &=\sum\limits_{k=1}^{K}\sum\limits_{d=1}^{n}f_k(d)\left(\left(\sum\limits_{i=1}^{\frac{n}{d}}2\varphi(i)\right)-1\right)\\ res&=\sum\limits_{k=1}^{K}\sum\limits_{d=1}^{n}f_k(d)\\ F_k(n)&=\sum\limits_{i=1}^{n}f_k(i)\\ &=\sum\limits_{i=1}^{n}g(i)-\sum\limits_{i=2}^{n}(-\mu(i))\sum\limits_{j=1}^{\frac{n}{i^{k+1}}}g(i^{k+1}j)\\ &=\sum\limits_{i=1}^{n}\mu(i)\sum\limits_{j=1}^{\frac{n}{i^{k+1}}}g(i^{k+1}j)\\ &=\sum\limits_{i=1}^{\sqrt[k+1]{n}}\mu(i)g^{k+1}(i)\sum\limits_{j=1}^{\frac{n}{i^{k+1}}}g(j)\\ G(n)&=\sum\limits_{i=1}^{n}g(i)\\ g*\delta&=\beta\\ \sum\limits_{d|n}g(\frac{n}{d})&=[\exist i\in N^{*},i^2=n]\\ g*I&=[\exist i\in N^{*},i^2=n]\\ \sum\limits_{i=1}^{n}[\exist j\in N^{*},j^2=i]&=\sum\limits_{i=1}^{n}\sum\limits_{d|i}g(\frac{i}{d})\\ &=\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\frac{n}{d}}g(i)\\ &=G(n)+\sum\limits_{d=2}^{n}G(\frac{n}{d})\\ G(n)&=\sqrt{n}-\sum\limits_{d=2}^{n}G(\frac{n}{d})\\ \end{aligned} \]
杜教筛就完事了。
T3
对于两条序列，有如下结论和证明。
\[a\rightarrow b,c\rightarrow d \]
\[a\rightarrow d,c\rightarrow b \]
\[(a,b)\cap(c,d)=e,(a,e)+(e,b)+(c,e)+(e,d)=(a,d)+(c,b) \]
\[(a,b)\cap(c,d)=\emptyset,rt,LCA(a,b),LCA(c,d) \]
这样我们只需要找到每个点当了多少次起点或者终点，然后按照最小字典序组合起来就可以了。
\[fr=LCA(a,b),se=LCA(c,d) \]
\[(a,fr)+(fr,b)+(c,se)+(se,d)=(a,fr)+(fr,se)+(se,d)+(c,se)+(se,fr)+(fr,b) \]