本来是想练习一下离散化的,结果看到这道又有并查集又有离散化的题,于是就逝了逝
发现自己对并查集和离散化认识有点问题,于是写下这篇笔记总结一下。
看到这种给出几个条件判断矛盾的题,便想到了两种常见思路,一种是拓扑排序,一种是并查集。这道题由于是区间而不是像
然而,第一眼看上去没有头绪,但区间个数这种形式让我们想到前缀和,进一步思考,发现一个关键性质:
记 s[i]
为前 个数中 的数量。若区间 中 的数量为偶数,那么有 s[r] - s[l - 1]
为偶数,从而s[r]
与 s[l - 1]
同奇偶,同理,若区间 中 的数量为奇数, 那么有 s[r]
与 s[l - 1]
奇偶性相反。利用这一点,我们可以直接利用并查集判断 s[r]
与 s[l - 1]
的奇偶性是否有矛盾。为此,我们可以标记两个点的奇偶性是否相同,将相同的用并查集合并,不相同的怎么办呢?我们可以将数组扩大成两倍空间,若原来的总数为 , 则 fa[x + n]
用于记录和 fa[x]
奇偶性不同的关系(或更通俗的,敌人。这里可以把奇偶性相同的比作朋友,不相同的比作敌人,且满足敌人的敌人是朋友,敌人的朋友是敌人等关系)。由此我们可以得到下面这个关键代码:
for (int i = 0; i < m; i++) {
if (a[i].x == 0) { // 偶数,a[i].l 与 a[i].r 奇偶相同
if (find(a[i].l) == find(a[i].r + res) or find(a[i].r) == find(a[i].l + res)) {
cout << i << '\n';
return 0;
}
merge(a[i].l, a[i].r);
merge(a[i].l + res, a[i].r + res);
}
else { // 奇数,a[i].l 与 a[i].r 奇偶不同
if (find(a[i].l) == find(a[i].r) or find(a[i].l + res) == find(a[i].r + res)) {
cout << i << '\n';
return 0;
}
merge(a[i].l, a[i].r + res);
merge(a[i].r, a[i].l + res);
}
}
这样这道题大体思路已出来了,但值域到了 ,显然不能直接用值作为下标,为此,我们可以用离散化进行处理。
所谓离散化,就是把坐标(值,下标)等在保持相对大小不变时,将其映射到一个好处理的范围。例如:
1437 998244353 1000000007 314159
-> 1 3 4 2
实现离散化,可以先排序。由于相同的值离散化后也应相同,为此,最简单高效的方法是直接去重。
下面给出本题离散化代码,其他题的离散化部分也是类似思路:
sort(b, b + tot); // 排序
int res = unique(b, b + tot) - b; //去重
for (int i = 0; i < m; i++) { //由于排序 + 去重后元素满足单调性且不存在相同值,正好使用二分查找来找到离散化后的位置
a[i].l = lower_bound(b, b + res, a[i].l) - b;
a[i].r = lower_bound(b, b + res, a[i].r) - b; //注意这里l, r离散化时不应做区分(即对l,r分别做)只要相对位置对了就行了,不明白可以手动做几组模拟一下离散化过程(这种~~弱智~~问题不会只有我一开始不明白吧)
}
下面是本题完整代码: