多校e题

http://acm.gxu.edu.cn/contest/2/problems/

大意:n*m的场地,初始全白色,(x,y)位置的炸弹使同行同列反色,本身位置颜色不变。Q个操作,一种放炸弹,一种询问某一矩阵内黑色数量。1<=N,M,Q<=100000。

解法:放置炸弹操作可等价拆分成一次同行反色操作和一次同列反色操作 (特殊情况两炸弹同行或同列不影响拆分的正确性),用线段树或树状数组分别维护区间内行列操作数量和,询问某一矩阵范围内黑色格子数即为区间内:行操作和*列数+列操作和*行数-2*行操作和*列操作和。代码略。

原文地址:https://www.cnblogs.com/Undeadtoad/p/7049167.html