题目链接：
POJ 1733 Party Game
题意：
有n个数字，每个数字非0即1，有m条语句，每条语句：l,r,even/odd，表示l到r区间上有奇/偶个1.
问最多前多少条语句是正确的？
分析：
和POJ 3038 How many answers are wrong? http://acm.hdu.edu.cn/showproblem.php?pid=3038 类似。
用val[i]表示从i到根节点路径上含有1的数量的奇偶性。在寻找根节点的同时更新路径上的val。
比较麻烦的是数据范围。n<=1000000000，而m<=5000.
①：可以用map来标记各个读入点的次序，相当于有个代号，在map里没读入的话就添加进map
在find()和mix()函数里相当于是对代号的操作，代号具有唯一性。
由于m<=5000，所以最多会读入10000个相异的数，那么对于pre数组和val数组都是可以接受的了。
②：hash思路。同样是代号的想法，把l(或r) mod maxn 值相同的归在一类，
用head数组的下标记录这类，head的数值表示最后一类的读入位置。和最短路里链式前向星的查找类似。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;const int maxn=10010;int pre[maxn],val[maxn],n,m,l,r,w;
char s[10];int find(int x)
{if(pre[x]==x) return x;int tmp=find(pre[x]);val[x]=(val[x]+val[pre[x]])%2;return pre[x]=tmp;
}int mix(int x,int y,int z)