题目大意
有一个 $n$行、$m$列的方格，每个格子上可以写 $0$ 或 $1$两种数字，一开始每个格子上都写着数字 $1$。
小爱会进行 $k$ 轮反转操作，每轮游戏他会选择一块区域，左上角为$(x_1, y_1)$，右下角为 $(x_2, y_2)$，并将该区域内所有的数字反转(即原来为 $1$ 的反转为 $0$ ，原来为 $0$ 的反转为 $1$) 。
请问， $k$ 轮过后，整个方格中仍为 $1$ 的方格的数量。
数据范围
$ 1 \le k \le 10^5 $
$1 \le n,m,x_i,y_i \le 10^9$
算法思路
本题采用扫描线算法，扫描线需要使用一种叫做线段树的数据结构。为了更好的理解本题和阅读的连贯性，引用OI-WIKI关于扫描线算法的部分内容。
引入 Atlantis 问题
在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。
根据图片可知总面积可以直接暴力即可求出面积，如果数据大了怎么办？这时就需要讲到扫描线算法。
现在假设我们有一根线，从下往上开始扫描：
- 如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。
- 我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1，每遇到一个矩形时，我们知道了标记为 1 的边，我们就加进来这一条矩形的长，等到扫描到 -1 时，证明这一条边需要删除，就删去，利用 1 和 -1 可以轻松的到这种状态。
- 还要注意这里的线段树维护的并不是线段的一个端点，而指的是一段区间。
- 根据数据范围可能需要进行离散化或动态开点。
本题与Atlantis区别
- Atlantis是计算面积而本题是计算方格数量，计算方法类似，但方格数量与线段长度在处理上还是有些区别的。
- Atlantis一段区间可以被多个矩形覆盖，被一个矩形覆盖和多个矩形覆盖效果一样。但方格计数不同，覆盖奇数次等于覆盖一次，偶数次等于没有覆盖。这个规律提示我们可以使用异或，奇偶性来完成题目。
分享一下，我自己解决这两个问题方法。时间上并非最优，上海月赛测$400ms$左右，但很好理解。
首先，把格子横坐标离散化。离散化后，若有$M$个不同的 $x$ 坐标值，分别对应原始值$raw(1),raw(2),raw(3),...,raw(M)$。扫描线至多被分成$M-1$段，其中第 $i \space (1\le i \le M-1)$ 段为区间$[raw(i),raw(i+1))$或$[raw(i),raw(i+1)-1]$。左闭右开我们不会重复统计端点的格子，且 $i$ 区间内部有$raw(i+1) - raw(i)$个方格。建立数组 $t$ ，用$t[i]$ 记录第 $i$ 段格子上写 $0$ 的格子数量，当然后面我们需用线段树维护 $t[i]$ 。
若离散化后，某次更新$x_1=3 ,x_2=5$，需要更新区间 $3$ 与区间 $4$。$x_2$ 这个位置方格还有没计数啊。
这个问题思考了一段时间。我们可再建立数组 $w$，用 $w[x]$ 记录离散化后 $x$ 这个点被操作次数。线段树同时利用数组 $t$ 和 $w$ 就可以计算出闭区间写 $0$ 的格子的数量。
void changeSeg(int p, int l, int r, int x) {
if (l <= t[p].l && t[p].r <= r) {
t[p].add += x;//加标记
t[p].len = a[t[p].r+1] - a[t[p].l] - t[p].len;//0，1数量互换
return;
}
spread(p);
int mid = (t[p].l+t[p].r)>>1;
if (l <= mid) changeSeg(p<<1, l, r, x);
if (mid < r) changeSeg(p<<1|1, l, r, x);
t[p].len = t[p<<1].len+t[p<<1|1].len;
}void changePoint(int p,int l,int r,int x){
if (l <= t[p].l && t[p].r <= r) {//包含这个端点的区间根据w[l]数值进行更新
if((t[p].add + w[l] + x) & 1)
t[p].len++;
else
t[p].len--;
w[l] += x;
return;
}
spread(p);
int mid = (t[p].l+t[p].r)>>1;
if (l <= mid) changePoint(p<<1, l, r, x);
if (mid < r) changePoint(p<<1|1, l, r, x);
t[p].len = t[p<<1].len+t[p<<1|1].len;
}
注意这两个函数很像，为了节约代码行数可以合并成为一个函数，但会导致思路不清晰。
for (int i = 1; i < k; ++i) {
int l = query(e[i].x1),r = query(e[i].x2);
if(r > l)
changeSeg(1, l, r-1, e[i].k);//区间更新
changePoint(1, r, r, e[i].k);//单点更新
if(e[i+1].y != e[i].y){
ans += 1ll * t[1].len * (e[i+1].y - e[i].y);
}
}总体来说就是更新两次，先更新线段树维护区间，再更新端点，这样可确保不多不少的统计。若 $l,r$ 相等则只进行单点更新即可。
更新一下，一直以来对changePoint不顺眼，再想能不能只保留一个changeSeg。如果只保留changeSeg函数，那必须让changeSeg函数可以处理单点更新。猛然发现，上述区间更新方法保持不变，一个点也是可以构成区间，只需让起点不变，终点加一，这样更新时$x2 > x1$。
举例若离散化后，某次更新$x_1=3 ,x_2=4$。需要更新区间为$3$，涉及格子数量为$[raw(3),raw(4)-1]$，假设此时是单点更新，那么$raw(4)$就会恰好比$raw(3)$大$1$，就是更新$[raw(3),raw(3)]$这个点。
for (int i = 1; i <= k; ++i) {
int x1, y1, x2, y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
e[(i<<1)-1] = (edge){y1, x1, x2+1, 1};
e[i<<1] = (edge){y2+1, x1, x2+1, -1}; //加入线段
a[(i<<1)-1] = x1, a[i<<1] = x2+1;
}
如此时间会更加优秀~~
评论 (0)