【奇偶传递 扩展域】 奇偶游戏

传送门

题意

给定一个(N)表示一个(01)序列(S)的长度，给定(M)个指示，每个指示一个(l、r)，以及说明关系的字符串

• (（l，r，odd）)，表示(（l，r）)有偶数个(1)
• (（l，r，even）)，表示(（l，r）)有奇数个(1)

求出在多少个指示后出现矛盾

数据范围

(N leq 10^{9}, M leq 10000)

题解

将每个给定的都看作是条件，同样用到前缀和，(x)表示(l-1)，(y)表示 (r)

• 如果有偶数个，合并(x_{odd})和(y_{odd})，(x_{even})和(y_{even})，说明(x)为奇数和(y)为奇数可以互相推出，(x)为偶和(y)为偶也可以互相推出。

• 如果有奇数个，那么合并(x_{odd})和(y_{even})，(x_{even})和(y_{odd})，说明(x)为奇数和(y)为偶数可以互相推出，(x)为偶和(y)为奇也可以互相推出。

相当于在无向图中维护连通性关系，满足传递性，(l)的奇数域即离散化后的自身，偶数域表示为将(l+N)后离散化的值，(r)同理

• 因为一次性合并两个域名，所以只需要判断其中一个即可

  • 当(l)和(r)的奇偶性不同时，如果(x_{odd} = y_{odd})或(x_{even} =y_{even}) 即矛盾

  • 当奇偶性相同时，如果(x_{odd} = y_{even})或(x_{even}=y_{odd})时矛盾

Code

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)

const int N=1e5+10;


int fa[N*2];
int n,m,cnt;
unordered_map<int,int> rec;

int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}

void merge(int a,int b)
{
    int pa=find(a),pb=find(b);
    if(pa!=pb)
    {
        fa[pa]=pb;
    }
}
int disperse(int x)
{
    if(!rec[x]) rec[x]=++cnt;
    return rec[x];
}
int main()
{
    cin>>n>>m;
    rep(i,0,N*2+1) fa[i]=i;
    char op[5];int l,r;
    int diff;

    rep(i,1,m+1)
    {
        cin>>l>>r>>op;
        l=disperse(l-1),r=disperse(r);
        int lodd=l,leven=disperse(l+n),rodd=r,reven=disperse(r+n);
        if(op[0]=='e') diff=0;
        else diff=1;
        if(diff)
        {
            if(find(lodd) == find(rodd))
            {
                cout<<i-1<<endl;
                return 0;
            }
            merge(lodd,reven);merge(leven,rodd);
        }
        else 
        {
            if(find(lodd)==find(reven))
            {
                cout<<i-1<<endl;
                return 0;
            }
            merge(lodd,rodd);merge(leven,reven);
        }
    }
    cout<<m<<endl;
}