CEOI - PARITY

Source: CEOI'99 - PARITY
Tags: Data Structures

Problem:
Cho một dãy nhị phân có độ dài N và M điều kiện mô tả dãy nhị phân đó. Mỗi điều kiện gồm 3 tham số có dạng (x, y, state), trong đó 1 ≤ x ≤ y ≤ N và state là even hoặc odd mô tả số lượng chữ số 1 trong dãy con từ x đến y là chẵn hay lẻ. Tìm số K cho biết rằng, tồn tại dãy nhị phân thỏa K điều kiện đầu tiên, nhưng từ điều kiện K + 1 trở đi thì không tồn tại dãy nhị phân thỏa mãn nữa.
N ≤ 1e9. M ≤ 5000.

Ví dụ:
Input:
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

Output:
3

Explanation:
Dãy nhị phân thỏa mãn đến điều kiện thứ 3 là: 1101001010

Solution:
Gọi r[x] là vị trí trái nhất mà nửa khoảng (r[x], x] xác định được giá trị (số lượng chữ số 1 là chẵn hay lẻ) và s[x] là giá trị nửa khoảng (r[x], x] (s[x] = 0 nếu số lượng chữ số 1 là chẵn và s[x] = 1 nếu là lẻ).
Với mỗi điều kiện (x, y, state), coi x = x - 1, tức lúc này (x, y, state) là giá trị của nửa khoảng (x, y], đồng thời state nhận giá trị 0 nếu state = even hoặc nhận giá trị 1 nếu state = odd, ta có thể có 3 trường hợp sau:

r[x] = r[y]:

Lúc này ta kiểm tra nếu s[x] xor s[y] = state thì ta có thể tiếp tục, nếu không thì không tồn tại dãy nhị phân nào phù hợp, ta dừng tại đây.

r[x] > r[y]:

Lúc này (r[y], r[x]] chưa xác định được giá trị, vì nếu đã xác định được thì r[x] đã bằng r[y], do đó luôn có thể tồn tại dãy nhị phân thỏa các điều kiện đã cho. Đồng thời, khi này ta xác định được giá trị của (r[y], r[x]], do đó ta gán r[r[x]] = r[y] và s[r[x]] = s[x] xor s[y] xor state.

r[x] < r[y]:

Lúc này (r[x], r[y]] chưa xác định được giá trị nên cũng luôn tồn tại dãy nhị phân thỏa các điều kiện đã cho. Ta cũng đồng thời gán lại giá trị r[r[y]] = r[x] và s[r[y]] = s[x] xor s[y] xor state.

Tuy nhiên khi gán lại các giá trị r[x] và s[x], ta cũng phải gán lại các giá trị r[y] và s[y] có r[y] = x (do ta mở rộng vùng xác định được giá trị đối với x thì những thằng y nhận x làm giới hạn vùng của nó cũng phải được mở rộng ra cho hợp lý). Đối với bước này thì ta có thể xử lý gọn gàng sạch sẽ bằng DSU - Disjoint Set Union: coi giới hạn trái nhất của x làm gốc của cây và lưu thêm giá trị của vùng (lý do tại sao tui đặt mảng r[x] là vị trí trái nhất xác định được giá trị :< r[x] ở đây là root[x] chứ hông phải right[x] đâu nhaaaaa).
Mặc dù N có thể tới 1e9 nhưng mà ta chỉ có M điều kiện, tức là chỉ cần xét tối đa 2M điểm, do đó N ở đây hơi vô dụng :v ngoại trừ mang tính chất đánh lừa, và do chỉ xét 2M điểm nên ta cũng cần nén các giá trị lại.
Độ phức tạp: O(M * log(2M))

Code: (không hiểu sao xài cin, cout mình lại bị lỗi trên POJ :/)
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

int n, m, a[5000], b[5000], c[5000], r[10000], s[10000];
vector <int> x;

int root(int u) {
    if (r[u] == -1) return u;
    int v = r[u];
    r[u] = root(r[u]);
    s[u] ^= s[v];
    return r[u];
}

bool unite(int a, int b, int c) {
    a = lower_bound(x.begin(), x.end(), a) - x.begin();
    b = lower_bound(x.begin(), x.end(), b) - x.begin();
    int u = root(a), v = root(b);
    if (u > v)
        r[u] = v, s[u] = s[a] ^ s[b] ^ c;
    else if (u < v)
        r[v] = u, s[v] = s[a] ^ s[b] ^ c;
    else return (s[a] ^ s[b]) == c;
    return true;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d ", &a[i], &b[i]);
        c[i] = getchar() == 'o';
        getchar(); getchar(); getchar();
        x.push_back(--a[i]); x.push_back(b[i]);
    }
    sort(x.begin(), x.end());
    memset(r, -1, sizeof r);
    for (int i = 0; i < m; ++i)
        if (!unite(a[i], b[i], c[i])) {
            printf("%d", i); return 0;
        }
    printf("%d", m);
}