【BZOJ 2877】[NOI2012] 魔幻棋盘

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2877
神犇题解Ⅰ:http://www.cnblogs.com/Randolph87/p/3795729.html
神犇题解Ⅱ:https://blog.sengxian.com/solutions/bzoj-2877

解题报告

首先这货需要有一个结论: $\gcd ({a_1},{a_2}, \cdots ,{a_n}) = \gcd ({a_i}, {a_1} – {a_2},{a_2} – {a_3}, \cdots ,{a_{n – 1}} – {a_n})$
证明的话,想一想辗转相除法就可以啦!
酱紫的话,一维情况我们维护一个差分就可以啦!

现在考虑二维的情况,每一维直接用线段树肯定是不可取的
于是我们考虑答案的表达式: $\gcd (gcd({a_{i,j}},{a_{l,j}} – {a_{l + 1,j}}, \cdots ,{a_{r – 1,j}} – {a_{r,j}}), \cdots ,gcd({a_{i,k}},{a_{l,k}} – {a_{l + 1,k}}, \cdots ,{a_{r – 1,k}} – {a_{r,k}}))$
将每一个 $gcd()$ 的第一项全部提出来,就是 ${\rm{gcd}}({a_{l,j}}, \cdots ,{a_{l,k}})$
这个只有一维,可以用上文提到的情况来解决
剩下的部分每一次修改还是会改到 $O(n)$ 个点
这样是不优雅的,于是考虑在第二维也差分一次的话
那么每一次需要修改的点就只有4个了
于是就可以用二维线段树维护啦!

Leave a Reply

Your email address will not be published. Required fields are marked *