T1
题意:已知 \(P=10^{18}+31\) 为质数且存在原根 \(g=42\) ,记 \(A_0\) 为 \(795484359100928850\) ,\(A_k=f(A_{k-1})\) ,其中 \(0 < f(x) < P\) 且满足 \(g^{f(x)} \equiv x (mod P)\) ,可证明这样 \(f(x)\) 唯一存在,每次查询一点 \(f(x)\) 的取值,\(1 \le x \le 10^5\)。
事实上,此题和原根一点关系都没有。
观察样例,发现他给了我们 \(10^5\) 时候的取值。
那我们就可以反推了,由 \(A_{k}\) 推出 \(A_{k-1}\) 。
记得用 \(int128\) 。
T2
见此篇题解 。
T3
构造题
T4
题意:给出一个长度为 \(n\) 的 \(a\) 序列,每次询问给出 \(l1,r1,l2,r2\) ,求 \(a_x+a_y\) 的最大值,其中 $l1 \le x \le r1 , l2\le x \le r2 $,且 \(a_x/2 \le a_y < a_x\) 。
用主席树即可解决。