|
|
思路：
這題是道好題！
假比確定了 [2, 4]、[5, 6]、[7, 8] 的奇偶性
[4, 5] 的奇偶性無(wú)法得知
[2, 6] 的奇偶性是知道的
所以只有詢問(wèn)的區(qū)間符合以下要求：
1. 頭部和某個(gè)已知區(qū)間的頭部重合
2. 尾部和某個(gè)已知區(qū)間的尾部重合
3. 區(qū)間內(nèi)每一段都是已知的
才能得出結(jié)論
我只想到這一步，然后用鏈表寫(xiě)了一遍，TLE 了。上網(wǎng)搜解題報(bào)告，看到“并查集”三字，恍然大悟。嗎的太牛逼了。
我們把首尾相接的多個(gè)已知區(qū)間歸為一類。
將這多個(gè)區(qū)間的尾部的點(diǎn)歸在同一個(gè)集合中。
它們的父親就是最左邊區(qū)間頭部。
它們的權(quán)值就是從左邊區(qū)間頭部的到自己的這段區(qū)間的奇偶性。
插入?yún)^(qū)間 [i, j] 的時(shí)候，首先查找 i, j 對(duì)應(yīng)的父親。就是 find 操作。
如果它們的父親相同，則表明它們處在同一個(gè)段的多個(gè)已知區(qū)間中。
那么 i, j 的權(quán)值相減，就很容易得出 [i, j] 的奇偶性了。
如果它們的父親不同，則需要將 i, j 分別對(duì)應(yīng)的區(qū)間段關(guān)聯(lián)起來(lái)。也就是 union 操作。
這時(shí)候要注意判斷 i, j 父親的位置先后。因?yàn)檫@個(gè) WA 了一次。
由于節(jié)點(diǎn)的位置分得很散，用 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;
}
|