原题链接
更好的阅读体验

题目描述

小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。

输出格式
输出一个整数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

前缀和+异或性质+并查集+离散化

我们可以用sum数组表示序列S的前缀和,那么会得到以下性质.

1. s[l~r]有偶数个1,等价于sum[l-1]与sum[r]奇偶性相同 (1+0=1 0+0=0,1是奇数,0是偶数)
2. s[l~r]有奇数个1,等价于sum[l-1]与sum[r]奇偶性不同 (1+1=0 0+1=0,1是奇数,0是偶数)

以下是传递关系细目表

1. 如果说$x_1$和$x_2$奇偶性质相同,$x_2$与$x_3$奇偶性质相同,那么$x_1$和$x_3$也相同
2. 如果说$x_1$和$x_2$奇偶性质相同,$x_2$与$x_3$奇偶性质不同,那么$x_1$和$x_3$也不同
3. 如果说$x_1$和$x_2$奇偶性质不同,$x_2$与$x_3$奇偶性质不同,那么$x_1$和$x_3$就相同
4. 上面看清楚地啊,别看错了,尤其是相同和不同

离散化:这道题目N超大,但是M却少,所以记得离散化.(最讨厌离散化了)

异或:我们可以通过异或来满足上面的传递关系,具体可以看代码.我懒了,主要是太久没有写题解了,今天晚上要写至少八篇,好累哎.QwQ

不懂得记得call下博主啊!不要将问题留在心里!!!

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010<<1;
struct node
{
    int l,r,ans;
} q[N];
int a[N],fa[N],d[N],n,m,t_n;
int get(int x)
{
    if (x==fa[x])
        return x;
    int root=get(fa[x]);
    d[x]^=d[fa[x]];//异或
    return fa[x]=root;
}
inline int read_init()//离散化
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        char str[5];
        scanf("%d%d%s",&q[i].l,&q[i].r,str);
        q[i].ans=(str[0]=='e'?0:1);
        a[++t_n]=q[i].l-1;
        a[++t_n]=q[i].r;
    }
    sort(a+1,a+1+t_n);
    n=unique(a+1,a+1+t_n)-a-1;//去重
}
inline int work()
{
    read_init();
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x=lower_bound(a+1,a+1+n,q[i].l-1)-a;//离散化后要找数
        int y=lower_bound(a+1,a+1+n,q[i].r)-a;
        int p=get(x),q2=get(y);
        if (p==q2)
        {
            if ((d[x]^d[y])!=q[i].ans)//变量要相等,但是却不相等了.
            {
                cout<<i-1<<endl;
                return 0;
            }
        } 
        else
        {
            fa[p]=q2;//合并merge.两方代码就懒得写函数了,见谅
            d[p]^=d[x]^d[y]^q[i].ans;//统统异或
        }
    }
    cout<<m;//数据过于优秀,一个问题都没有
}
int main()
{
    work();
    return 0;
}