本题为并查集入门者的必做好题,过者可以再去做一下P2024 [NOI2001]食物链
分析:
我们在序列S上可以建立前缀和数组pre[MaxS]。
若S[l ~ r]有偶数个1,则pre[l−1]与pre[r]奇偶性相同;反之则相反。
而这些奇偶性的关系是可传递的,如果发生又同奇偶又异奇偶就能找到矛盾。
所以这道题我用并查集维护,提供两种思路。
idea 1:扩展域并查集
我们可以把每个节点x拆成xodd和xeven。
如果pre[x]与pre[y]奇偶性相同就合并xodd与yodd,xeven与yeven
反之则相反。
如果条件要求同奇偶但xodd=yeven,或要求异奇偶但xodd=yodd,就矛盾了,输出前一个条件的编号。
使用按秩合并和路径压缩可以把并查集部分单次操作优化到O(α),但由于要离散化,所以复杂度还是有1个log,瓶颈在于离散化。
code: 代码太长放不下qwq。
idea 2: 边带权并查集
大体思路其实都差不多,这里使用边权异或值来维护奇偶性。
维护d[Maxm]数组,来阐述清楚节点x和getf(x)奇偶关系,间接表现同集合内两点奇偶关系。如果不在同一集合,进行合并,改变并入的那个集合的d[root]即可。
合并函数:
inline void unionf(int x, int y, int op) {
int fx = getf(x), fy = getf(y);
if (sze[fx] <= sze[fy]) sze[fy] += sze[fx], f[fx] = fy, d[fx] = d[x] ^ d[y] ^ op;
else sze[fx] += sze[fy], f[fy] = fx, d[fy] = d[x] ^ d[y] ^ op;
}
code:
const int Maxm = 1e4 + 5;
int n, m, f[Maxm], d[Maxm], sze[Maxm], a[Maxm]; char cmd[15];
inline int getf(int x) {
if (f[x] == x) return x;
int root = getf(f[x]);
d[x] ^= d[f[x]];
return f[x] = root;
}
inline void unionf(int x, int y, int op) {
int fx = getf(x), fy = getf(y);
if (sze[fx] <= sze[fy]) sze[fy] += sze[fx], f[fx] = fy, d[fx] = d[x] ^ d[y] ^ op;
else sze[fx] += sze[fy], f[fy] = fx, d[fy] = d[x] ^ d[y] ^ op;
}
struct State {
int l, r, opt;
State(int _l = 0, int _r = 0, int _op = 0) : l(_l), r(_r), opt(_op) {}
} que[Maxm / 2];
signed main(void) {
// file("");
read(n), read(m);
for (int i = 1, x, y; i <= m; i++) {
read(x), read(y), readstr(cmd);
que[i] = State(x, y, cmd[0] == 'o');
a[i] = x - 1; a[i + m] = y;
} sort(a + 1, a + (m << 1) + 1);
n = unique(a + 1, a + (m << 1) + 1) - (a + 1);
for (int i = 1; i <= n << 1; i++) f[i] = i, sze[i] = 1, d[i] = 0;
for (int i = 1, x, y; i <= m; i++) {
x = lower_bound(a + 1, a + n + 1, que[i].l - 1) - a;
y = lower_bound(a + 1, a + n + 1, que[i].r) - a;
if (getf(x) == getf(y)) {
if ((d[x] ^ d[y]) != que[i].opt) { writeln(i - 1); return 0; }
} else unionf(x, y, que[i].opt);
} writeln(m);
// fwrite(pf, 1, o1 - pf, stdout);
return 0;
}
刘兆鸭强啊!
LZZ 强啊
刘兆鸭强啊!