P9175[COCI2022-2023#4]Mreža题解前言我发现，有整体二分与主席树的地方总有莫队（不是那个莫队，是那个莫队）。知识点（树上）倍增，（树上）莫队，树状数组（“树”含量满满），分块。题意分析给定一棵树，每条边有一个权值\(v\)，以及可以用一个花费\(c\)将它变成更大的权值\(s\)。再给定一

SolutionP9030[COCI2022-2023#1]Berilij本题解转载翻译自官方题解：COCI2022/2023CONTEST1Part1让我们定义图形\(G\)，顶点代表飞船，边代表两艘飞船外部接触的情况。此外，让边的边权成为它所连接的圆之间的距离。现在的任务等同于为顶点找到非负值，使得每条边所连接的两个顶

分析对于一个从小到大（按编号排序）的长度为\(n\)的序列\(A\)，有性质：相邻两个数之差的绝对值为\(1\)的数量为\(n-1\)。那么，对于这道题，能使环剪开一条边使其按编号排序，必有相邻两个\(i,j\)，满足\((A_i-A_j=1)\)的数量为\(n-1\)。注意，因为这是个环，所以\(i,j\)大小关系不能

P9032考试题。发现\(g\)的值是若干个相同的段，且段数很少，因为每次取\(\gcd\)至少会将值域变为原来的一半。所以段数是\(\mathcal{O}(\logV)\)的。然后就可以从小到大枚举左端点，然后枚举\(g\)的值，找的是最远的满足\(\gcd(a_l,\dots,a_r)=g\)的\(r\)，这里可以使用二分