It can be solved by DisJoin-Set..

CEOI 1999

算法艺术 P88

倒,原来是初始化错了= =

倒,1e9啊...加了hash才过的,容易MLE

1e6的数组+mod 999983;

设s[a]为前a个数中1是否是奇数个

[code]

a b even的实质是s[a-1]=s

a b odd的实质是s[a-1]s [/code]

以前看到过这个题目的..

记得把第二行输入的那个数范围开大点..

害惨我了

分享一个另类的，不用并查集的做法：

#include <iostream>
#include <string>
#include <string.h>
struct B {
    int l,r;
    int isOdd;
    struct B* next;
};
using namespace std;
int getAns() {
    int n; cin >> n;
    int t; cin >> t;
    string pattern;
    struct B* h = NULL;
    for(int i=0;i<t;i++) {
        int l,r;
        cin >> l >> r;
        cin.get();
        cin >> pattern;
        bool isOdd = strcmp(pattern.c_str(), "odd") == 0;
        struct B* cur = new B;
        cur->l = l; cur->r=r; cur->isOdd= isOdd;cur->next = NULL;
        if(h == NULL) {
            h = cur;
        } else {
            struct B* last = NULL;
            struct B* start = h;
            while(true) {
                if(cur->l < start->l) {
                    cur->next = start;
                    if(last == NULL){
                        h = cur;
                    } else {
                        last->next = cur;
                    }
                    break;
                } else if(cur->l == start->l) {
                    if(cur->r == start->r) {
                        if(cur->isOdd == start->isOdd) {
                            break;
                        } else {
                            return i;
                        }
                    } else if(cur->r > start->r) {
                        cur->l = start->r+1;
                        cur->isOdd = cur->isOdd ^ start->isOdd;
                    } else {
                        int qieGeIsOdd = cur->isOdd ^ start->isOdd;
                        start->isOdd = cur->isOdd;
                        cur->l = cur->r+1;
                        cur->r = start->r;
                        start->r = cur->l-1;
                        cur->isOdd = qieGeIsOdd;
                    }
                }

                if(start->next == NULL) {
                    start->next = cur;
                    break;
                }
                last = start;
                start = start->next;
            }
        }
//        printf("[%s]", pattern.c_str());
    }
    return t;
}


int main() {
    cout << getAns();
}

学了用hash压缩，感谢楼下。
还有合并的时候要注意对称性，x和y合并同时也要把x'和y'合并

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

const int MAXN=10000;
const int SIZE=6007;
int L;
int n;
int ha[SIZE];
int fa[MAXN*3];
int find(int x) {
    return (x==fa[x])?x:fa[x]=find(fa[x]);
}
int get(int x) {
    ll t=x;
    x%=SIZE;
    while (ha[x]!=-1&&ha[x]!=t) {
        ++x;
        x%=SIZE;
    }
    ha[x]=t;
    return x;
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    REP(i,0,3*MAXN-1) fa[i]=i;
    memset(ha,-1,sizeof ha);
    cin>>L>>n;
    FOR(i,n) {
        int x,y;
        cin>>x>>y;
        int xx=get(x-1),yy=get(y);
        string s;
        cin>>s;
        if (s[0]=='o') {
            int u=find(xx),v=find(yy+MAXN);
            fa[u]=v;
            u=find(xx+MAXN),v=find(yy);
            fa[u]=v;
            if (find(xx)==find(yy)) {
                cout<<i-1<<endl;
                return 0;
            }
        } else {
            int u=find(xx),v=find(yy);
            fa[u]=v;
            u=find(xx+MAXN),v=find(yy+MAXN);
            fa[u]=v;
            if (find(xx)==find(yy+MAXN)||find(xx+MAXN)==find(yy)) {
                cout<<i-1<<endl;
                return 0;
            }
        }
    }
    cout<<n<<endl;
    return 0;
}

第一个和第6个点惨案。。。。。。。有帮忙看一下的吗

const
maxn=10000;
hash=6100;
var
f:array[0..maxn*2+100] of longint;
map:array[0..hash] of longint;
n,m,a,b,i,k:longint;
s:string;
function ha(x:longint):longint;
var
bri:longint;
begin
bri:=x mod hash;
while (map[bri]<>-1) and (map[bri]<>x) do bri:=(bri+1) mod hash;
map[bri]:=x;
exit(bri);
end;
function find(x:longint):longint;
begin
if f[x]=0 then exit(x);
f[x]:=find(f[x]);
exit(f[x]);
end;
procedure add(a,b:longint);
begin
a:=find(a);
b:=find(b);
if a<>b then f[a]:=b;
end;
begin
fillchar(map,sizeof(map),255);
fillchar(f,sizeof(f),0);
readln(n,k);
for i:=1 to k do
begin
readln(a,b,s);
a:=ha(a-1);
b:=ha(b);
if pos('e',s)<>0 then
begin
if find(a)=find(b+maxn) then break;
add(a,b);
add(a+maxn,b+maxn);
end
else
begin
if find(a)=find(b) then break;
add(a,b+maxn);
add(a+maxn,b);
end;
end;
writeln(i-1);
end.