题解 P2086 【[NOI2012]魔幻棋盘】

首先考虑一维的情况怎么做，我们发现用线段树维护无法区间修改。 观察发现 $\gcd(x,y)=\gcd(x,y-x)$，所以我们可以用线段树维护差分，然后单点修改，区间查询。 二维呢？ 二维线段树维护二阶差分就好啦！ 我们发现因为他每次都是从一个点往外扩展的，所以我们可以以 $(x,y)$ 为中心向四个方向差分。 修改的时候，我们可以大力分九种情况讨论。 - 修改矩形包含 $(X,Y)$ - 修改矩形包含 $x=X,y=Y$ 中的一条（四种） - 修改矩形全部位于 $(X,Y)$ 的一个方向（左上，右上，左下，右下） 通过二阶差分我们同样可以实现单点修改 然后就是愉快的coding时间啦！ [code](https://www.luogu.com.cn/paste/rtyanhx6)