原题：
题目描述
huyichen和xuzhenyi在玩一个游戏：他写一个由0和1组成的序列。 huyichen选其中的一段（比如第3位到第5位），问他这段里面有奇数个1 还是偶数个1。xuzhenyi回答你的问题，然后huyichen继续问。 xuzhenyi有可能在撒谎。huyichen要检查xuzhenyi的答案，指出在xuzhenyi的第几个回答一定有问题。 有问题的意思就是存在一个01序列满足这个回答前的所有回答，而且不存在序列 满足这个回答前的所有回答及这个回答。
输入格式
第1行一个整数，是这个01序列的长度（≤1000000000)（≤1000000000) 第2行一个整数，是问题和答案的个数(≤5000)(≤5000)。 第3行开始是问题和答案， 每行先有两个整数，表示你询问的段的开始位置和结束位置。 然后是xuzhenyi的回答。odd表示有奇数个1，even表示有偶数个
输出格式
输出一行，一个数X,表示存在一个01序列满足第1到第X个回答， 但是不存在序列满足第1到第X+1个回答。如果所有回答都没问题，你就输出 所有回答的个数。
很明显，这道题是并查集（不要问我怎么看出来的）。
由于数据太大，需要离散化。
所谓离散化，就是把较大的一组数进行排序，然后对他们根据大小重新赋值，当数的大小不对数据本身有影响，只有大小对其有影响时，可以使用离散化。
离散化的标准姿势见 点这里
然而蒟蒻并不会标准姿势，说说自己的方法：
以本题为例，把所有的数据都存在nd结构体中
void init()
{
for(int i = ;i<=m;i++)
{
int x,y;
scanf("%d%d%s",&x,&y,c);
nd[i].p = x;//数组开三倍，p表示临时变量。一倍存左端点。
nd[i+m].p = y;//二倍存右端点。
nd[i].num = i;//每一倍都要给他们打上编号，一会排序时后会乱。
nd[i+m].num = i;if(c[]=='e')
{
nd[i+m+m].odd = ;//三倍存奇偶
}else
{
nd[i+m+m].odd = ;
}
}
}
读进来之后进行离散化。
void discretization()
{
for(int i = ;i<=*m;i++)
{
if(nd[nd[i].num].l==-)
{
nd[nd[i].num].l = cnt-;
}else
{
nd[nd[i].num].r = cnt;
}
if(nd[i+].p!=nd[i].p)
{
cnt++; //去重，不一样的时候再+1
}
}
for(int i = ;i<=m;i++)
{
nd[i].odd = nd[i+m+m].odd;从三倍搬回原数组
}
}
这样就离散完了。
接下来就是带权并查集的操作。
在合并和路径压缩的时候处理。
思路就是将一个区间右面的点认左面的点为父亲，两端区间合并的时候，根据奇偶性判断，0表示偶数，1表示奇数（有点懒，具体0或1见代码）。
int find(int x)
{
if(f[x]==x)
{
return f[x];
}
int fx = find(f[x]);
g[x] = (g[f[x]]+g[x])%;
return f[x] = fx;
}
最后上总代码：
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define N 105550
using namespace std;
char c[];
ll n;
int m;
int cnt = ;
struct node
{
int l;
int r;
int num;
int odd;
int p;
}nd[N+N+N];
int f[N];
int g[N];
int cmp(node a,node b)
{
return a.p < b.p;
}
void init()
{
for(int i = ;i<=m;i++)
{
int x,y;
scanf("%d%d%s",&x,&y,c);
nd[i].p = x;
nd[i+m].p = y;
nd[i].num = i;
nd[i+m].num = i;
nd[i].l = -;
nd[i+m].l = -;
if(c[]=='e')
{
nd[i+m+m].odd = ;
}else
{
nd[i+m+m].odd = ;
}
}
}
void discretization()
{
for(int i = ;i<=*m;i++)
{
if(nd[nd[i].num].l==-)
{
nd[nd[i].num].l = cnt-;
}else
{
nd[nd[i].num].r = cnt;
}
if(nd[i+].p!=nd[i].p)
{
cnt++;
}
}
for(int i = ;i<=m;i++)
{
nd[i].odd = nd[i+m+m].odd;
}
}
int find(int x)
{
if(f[x]==x)
{
return f[x];
}
int fx = find(f[x]);
g[x] = (g[f[x]]+g[x])%;
return f[x] = fx;
}
int ans;
bool flag;
void uion(int x,int y,int i)
{
int fx = find(x);
int fy = find(y);
if(fx==fy)
{
if((nd[i].odd==&&g[x]==g[y])||(nd[i].odd==&&g[x]!=g[y]))
{
ans = i-;
flag = ;
return ;
}
find(y);
find(x);
}else
{
f[fy] = fx;
g[fy] = (g[x]+g[y]+nd[i].odd)%;
find(x);
find(y);
}
}
void solve()
{
for(int i = ;i<=cnt;i++)
{
f[i] = i;
}
for(int i = ;i<=m;i++)
{
int l = nd[i].l;
int r = nd[i].r;
uion(l,r,i);
if(flag==)
{
printf("%d\n",ans);
return ;
}
}
printf("%d\n",m);
}
int main()
{
scanf("%lld",&n);
scanf("%d",&m);
init();
sort(nd+,nd++m+m,cmp);
discretization();
solve();
return ;
}