题目描述

blablabla

样例

blablabla

题目链接：https://www.acwing.com/problem/content/description/241/
参考博客：https://www.cnblogs.com/cytus/p/8999662.html
https://blog.csdn.net/weixin_33785108/article/details/93960657
分析：
even是偶数，odd是奇数。一开始，因为这个wa了。简直狗血。
输入 x y even 表示x到y这个区间里面的1的个数为偶数个。
那么考虑一下
1~y 和1~（x-1） 的奇偶性。
因为（x，y）为偶数个：
如果1~（x-1）为奇 ，则1~y为奇 （1~y = （1~x-1） + （x，y））。
则可知，当（x，y）之间的个数为偶数的时候，（1y）和（1x-1）的奇偶性相同。

同理可以推得，当（x，y）之间的个数为奇数时，（1y）和（1x-1）的奇偶性不同。

我们把上面区间当作前缀和sum考虑（即：区间(1~y) 就是sum[y]）。
注意，这里并不是求出sum数组，而是把sum看作变量。
我们同样需要建立一个d数组。
d[x]表示x与f[x]之间的奇偶性关系。奇偶性相同则为0，不同则为1。
路径压缩的时候，我们要不断的维护d数组，从而得到x与树根之间的关系

相同xor相同=相同0xor0=0
相同xor不同=不同0xor1=1
不同xor不同=相同1xor1=0
int Find(int x)
{
    if(f[x] == x) return x;
    int root = Find(f[x]);
    d[x] = d[x] ^ d[f[x]];
    return f[x] = root;
}

通过上述代码，我们能得到x与树根之间的关系。
在考虑如何合并两个x，y。并同时维护d数组。
为了方便简述：

我们设n为x的树根，m为y的树根。
现在我们已经知道了x到n的值d[x],y到m的值d[y]。现在很明显，我们要求的是d[n]。
我们知道x与y的奇偶性关系是result。
那么，result = d[x] ^ d[y] ^ d[n]。通过变换，我们可以得到d[n] = d[x] ^d[y] ^ ans。
所以，合并时候的d数组维护也就清楚了。

int n = Find(x1),m = Find(y1);
        if(n == m)
        {
            if(d[x1] ^ d[y1] == result)
                continue;
            else
            {
                printf("%d\n",i - 1); return ;
            }
        }
        else
        {
            f[n] = m;
            d[n] = d[x1] ^ d[y1] ^ result;
        }

同时，注意到范围，我们发现n的范围过大，但是m的范围比较小。所以

C++ 代码

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;

int N,M;
int d[20010],b[20010],f[20010];
int a[10010][3],n;

int Find(int x)
{
    if(f[x] == x) return x;
    int root = Find(f[x]);
    d[x] = d[x] ^ d[f[x]];
    return f[x] = root;
}

void init()
{
    scanf("%d",&N); scanf("%d",&M);
    for(int i = 1; i <= M; i ++)
    {
        int x,y;char str[10];
        scanf("%d%d%s",&x,&y,str);
        x --;
        b[++ n] = x; b[++ n] = y;
        if(str[0] == 'e')
        {
            a[i][0] = x; a[i][1] = y; a[i][2] = 0;
        }
        else
        {
            a[i][0] = x; a[i][1] = y; a[i][2] = 1;
        }
    }
    sort(b + 1,b + 1 + n);
    n = unique(b + 1,b + 1 + n) - b;
    for(int i = 1; i <= n;i ++)
        f[i] = i;
}

void work()
{
    for(int i = 1; i <= M; i ++)
    {
        int x = a[i][0],y = a[i][1],result = a[i][2];
        int x1 = lower_bound(b + 1,b + 1 + n,x) - b;
        int y1 = lower_bound(b + 1,b + 1 + n,y) - b;
        //printf("x1 = %d y1 = %d\n",x1,y1);
        int n = Find(x1),m = Find(y1);
        if(n == m)
        {
            if(d[x1] ^ d[y1] == result)
                continue;
            else
            {
                printf("%d\n",i - 1); return ;
            }
        }
        else
        {
            f[n] = m;
            d[n] = d[x1] ^ d[y1] ^ result;
        }
    }
    printf("%d\n",M); return ;
}

int main()
{
    init();
    work();
}