题意
【题意】
小A和小B在玩一个游戏。
首先，小A写了一个由0和1组成的序列S，长度为N。
然后，小B向小A提出了M个问题。
在每个问题中，小B指定两个数 l 和 r，小A回答 S[l~r] 中有奇数个1还是偶数个1。
机智的小B发现小A有可能在撒谎。
例如，小A曾经回答过 S[1~3] 中有奇数个1， S[4~6] 中有偶数个1，现在又回答 S[1~6] 中有偶数个1，显然这是自相矛盾的。
请你帮助小B检查这M个答案，并指出在至少多少个回答之后可以确定小A一定在撒谎。
即求出一个最小的k，使得01序列S满足第1~k个回答，但不满足第1~k+1个回答。
【输入格式】
第一行包含一个整数N，表示01序列长度。
第二行包含一个整数M，表示问题数量。
接下来M行，每行包含一组问答：两个整数l和r，以及回答“even”或“odd”，用以描述S[l~r] 中有奇数个1还是偶数个1。
补充：odd是奇数，even是偶数。
【输出格式】
输出一个整数k，表示01序列满足第1~k个回答，但不满足第1~k+1个回答，如果01序列满足所有回答，则输出问题总数量。
【数据范围】
N≤10^9,M≤10000
【输入样例】
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
【输出样例】
3题解
乍一看，这道题目没有什么思路。
但是仔细一想，我们发现了一个事情：\([2,4]\)和\([3,5]\)的奇偶性质互不影响，虽然有交集。
所以我们就可以认为即使两个区间有很大部分交集，可是他们的奇偶性质互相还是没有多大的影响的，除非他们的交集部分也明确给出了奇偶或者可以算出奇偶。
但是加入给你一个区间：\([1,3],[4,5]\)如何合并成\([1,5]\)的奇偶性质呢？
很明显我们可以化成\((0,3],(3,5]\)，然后合并成\((0,5]\)的奇偶性质，然后用个权值并查集就OK了。
但是\(n\)这么大！
那我们就离散化呀！！！！
离散化的正确性怎么保证？
我们设\([a,b]\)区间中，没有任何一个子区间能够确定奇偶性质，那么我们就可以把\([a,b]\)化成一个数字，奇数就是\(1\)，偶数就是\(0\)。
但是为了离散化的方便，我们可以把数字排序起来，如果间隔只是\(1\)，那么离散化值差就是\(1\)，但是如果间隔大于\(1\)，离散化之差就是\(2\)。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 41000
using namespace std;
int fa[N],val[N];
int findfa(int x)
{
if(fa[x]==x)return x;
int y=findfa(fa[x]);val[x]=val[x]^val[fa[x]];fa[x]=y;
return y;
}
struct problem
{
int l,r,type;
}a[N];
int ls[N],what[N],cnt;
bool cmp(int x,int y){return ls[x]<ls[y];}
int n,m,nn;
int main()
{
scanf("%d%d",&nn,&m);
for(int i=1;i<=m;i++)
{
char ss[20];
scanf("%d%d%s",&ls[(i<<1)-1],&ls[i<<1],ss+1);
what[(i<<1)-1]=(i<<1)-1;what[i<<1]=i<<1;a[i].type=(ss[1]=='o');
}
sort(what+1,what+(m<<1)+1,cmp);
ls[0]=ls[1]-2;
for(int i=1;i<=(m<<1);i++)
{
int x=what[i],y=what[i-1];
if(ls[x]>ls[y]+1)cnt+=2;
else if(ls[x]==ls[y]+1)cnt++;
if(x&1)a[(x+1)>>1].l=cnt;
else a[(x+1)>>1].r=cnt;
}
//离散化
for(int i=1;i<=cnt;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
a[i].l--;
int tx=findfa(a[i].l),ty=findfa(a[i].r);
if(tx==ty)
{
if(val[a[i].l]^val[a[i].r]!=a[i].type)
{
printf("%d\n",i-1);
return 0;
}
}
else
{
fa[tx]=ty;
val[tx]=val[a[i].l]^val[a[i].r]^a[i].type;
}
}
//乱搞
printf("%d\n",m);
return 0;
}