(又见POJ1733,VIJOS1112)
有人用并查集还有哈希，不知道为什么，我没有用他们，就用了一个排序二叉树（STL中的std::map）。然后就AC了。
思路：
对每一个点，记录其前驱和后驱（如果有），以及到前驱和后驱的线段上1出现的奇偶性。
每次读入一条线段时，插入分四种情况：
![URAL1003[Parity] - 天之骄子 - 天之骄子的家](https://blog.boleyn.su/wp-content/uploads/2010/03/5351683732200252726.jpg "URAL1003[Parity] - 天之骄子 - 天之骄子的家")
黑线为某条已有线段。
黄线代表，左端与一条已有线段重合，且右端在这条线段及其衍生出的线段上，这样，就将图中第二条黑线段（左数，后同）分为第二红点到d和d到第三红点两条线段。
绿线代表，左端与一条已有线段重合，且右端在这条线段及其衍生出的线段外，这样，就在图中增加一条右端红点到f的线段。
粉红与蓝色线段同上面对称。
并且，这时候是不能推出矛盾的。
如果读入线段上的点不与任何已有线段有公共点，就直接插入，并且不能推出矛盾。
若两端都有公共点，就扫描整条线段，看是否有矛盾。
具体的还是看我的CODE吧。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-3-9
DESCRIPTION:
$DESCRIPTION
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <cstring>
using std::memset;
#include <string>
using std::string;
#include <vector>
using std::vector;
using std::pair;
using std::make_pair;
#include <map>
using std::map;
class Question
{
int length;
int Q;
map<int,pair<int,bool> > record_l,record_r;
bool dfs_judge_l(int l,int r,bool isEven)
{
map<int,pair<int,bool> >::iterator it;
if ((it=record_l.find(l))!=record_l.end())
{
if (it->second.first==r)
return it->second.second==isEven;
else if (it->second.first>r)
{
//it->first to it->second.first it->second.second
record_l[r+1]=make_pair(it->second.first,isEven xor it->second.second);
//it->first to r isEven
it->second=make_pair(r,isEven);
return dfs_judge_r(r+1,record_l[r+1].first,record_l[r+1].second);
}
else
{
return dfs_judge_l(it->second.first+1,r,isEven xor it->second.second);
}
}
else
{
record_l[l]=make_pair(r,isEven);
return true;
}
}
bool dfs_judge_r(int l,int r,bool isEven)
{
map<int,pair<int,bool> >::iterator it;
if ((it=record_r.find(r))!=record_r.end())
{
if (it->second.first==l)
return it->second.second==isEven;
else if (it->second.first<l)
{
//it->second.first to it->first it->second.second
record_r[l-1]=make_pair(it->second.first,isEven xor it->second.second);
//l to it->first isEven
it->second=make_pair(l,isEven);
return dfs_judge_l(record_r[l-1].first,l-1,record_r[l-1].second);
}
else
{
return dfs_judge_r(l,it->second.first-1,isEven xor it->second.second);
}
}
else
{
record_r[r]=make_pair(l,isEven);
return true;
}
}
public:
bool read()
{
cin>>length;
if (length==-1) return false;
cin>>Q;
return true;
}
void solve()
{
int l,r;
string answer;
int answerq=1;
for (;answerq<=Q;answerq++)
{
cin>>l>>r>>answer;
if (!dfs_judge_l(l,r,answer==“odd”)) break;
if (!dfs_judge_r(l,r,answer==“odd”)) break;
}
cout<<answerq-1<<endl;
for (;answerq<Q;answerq++)
cin>>l>>r>>answer;
record_l.clear();
record_r.clear();
}
};
class Application
{
public:
int run()
{
Question q;
while (q.read()) q.solve();
return 0;
}
};
int main()
{
Application app;
return app.run();
}
![URAL1010[Discrete Function] - 天之骄子 - 天之骄子的家](https://blog.boleyn.su/wp-content/uploads/2010/03/5413889702053330904.jpg "URAL1010[Discrete Function] - 天之骄子 - 天之骄子的家")