题解 P2086 【[NOI2012]魔幻棋盘】
devout
2020-11-26 13:56:41
首先考虑一维的情况怎么做,我们发现用线段树维护无法区间修改。
观察发现 $\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)