|
|
思路：
这题是道好题！
假比确定了 [2, 4]、[5, 6]、[7, 8] 的奇偶性
[4, 5] 的奇偶性无法得知
[2, 6] 的奇偶性是知道的
所以只有询问的区间符合以下要求：
1. 头部和某个已知区间的头部重合
2. 尾部和某个已知区间的尾部重合
3. 区间内每一段都是已知的
才能得出结论
我只想到这一步，然后用链表写了一遍，TLE 了。上网搜解题报告，看到“并查集”三字，恍然大悟。吗的太牛逼了。
我们把首尾相接的多个已知区间归为一类。
将这多个区间的尾部的点归在同一个集合中。
它们的父亲就是最左边区间头部。
它们的权值就是从左边区间头部的到自己的这段区间的奇偶性。
插入区间 [i, j] 的时候，首先查找 i, j 对应的父亲。就是 find 操作。
如果它们的父亲相同，则表明它们处在同一个段的多个已知区间中。
那么 i, j 的权值相减，就很容易得出 [i, j] 的奇偶性了。
如果它们的父亲不同，则需要将 i, j 分别对应的区间段关联起来。也就是 union 操作。
这时候要注意判断 i, j 父亲的位置先后。因为这个 WA 了一次。
由于节点的位置分得很散，用 hash 存放。
 #include <stdio.h>
#define HASH_SIZE (1 << 18)
#define NODES_NR 65536
  struct node  {
 struct node *root, *next;
int idx, val;
 };
struct node *hash[HASH_SIZE], nodes[NODES_NR];
int nodes_cnt;
inline void find(struct node *t)
{
static struct node *stk[NODES_NR];
int i;
for (i = 0; t->root != t; t = t->root)
stk[i++] = t;
  for (i--; i >= 0; i--) {
stk[i]->val += stk[i]->root->val;
stk[i]->root = t;
 }
}
inline struct node *insert(int idx)
{
int h;
struct node *t;
h = idx & (HASH_SIZE - 1);
for (t = hash[h]; t; t = t->next) {
if (t->idx == idx)
break;
}
if (!t) {
t = &nodes[nodes_cnt++];
t->root = t;
t->idx = idx;
t->next = hash[h];
hash[h] = t;
}
return t;
}
inline int solve(int start, int end, int val)
{
struct node *a, *b;
a = insert(start);
b = insert(end);
find(a);
find(b);
if (a->root == b->root)
return ((b->val - a->val) & 1) == val;
val -= b->val;
val += a->val;
a = a->root;
b = b->root;
if (a->idx < b->idx) {
b->root = a;
b->val = val;
} else {
a->root = b;
a->val = -val;
}
return 1;
}
int main()
{
int n, i, x, a, b;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &n, &x);
for (i = 0; i < x; i++) {
scanf("%d%d%s", &a, &b, str);
if (!solve(a, b + 1, str[0] == 'o'))
break;
}
printf("%d\n", i);
return 0;
}
|