拓展域并查集好题(也许是食物链前置题?)
考虑转化题述关系
1. $[l,r]$有奇数个1:$[0,l-1]$的1的个数的奇偶性与$[0,r]$不同,因而可推出$[0,l-1]$的1的个数为奇数等价与$[0,r]$的1的个数为偶数,$[0,l-1]$的1的个数为偶数等价与$[0,r]$的1的个数为奇数
2. $[l,r]$有偶数个1:$[0,l-1]$的1的个数的奇偶性与$[0,r]$相同,因而可推出$[0,l-1]$的1的个数为奇数等价与$[0,r]$的1的个数也为奇数,$[0,l-1]$的1的个数为偶数等价与$[0,r]$的1的个数也为偶数
考虑用拓展域并查集维护这些关系:(在同一集合中表示等价,即要么同时成立,要么都不成立)
对于1,合并even(l-1),odd(r);合并odd(l-1),even(r).
对于2,合并even(l-1),even(r);合并odd(l-1),odd(r).
不妨设even(x)=x,odd(x)=x+n,即可用普通并查集维护了,总复杂度$O(N+M)$.
但由于$N\le 10^9$,需要进行离散化,复杂度变为$O(MlogM)$.
//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
typedef long long ll;
typedef std::pair<ll,ll> pll;
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
else c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
bool umin(ll &a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
bool umax(ll &a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
ll abs(ll x)
{
return x>0?x:-x;
}
/**********/
#define MAXN 100011
struct ufs
{
ll fa[MAXN];
void build(ll n)
{
for(ll i=0;i<=n;++i)fa[i]=i;
}
ll find(ll x)
{
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void uni(ll u,ll v)
{
u=find(u),v=find(v);
fa[u]=v;
}
bool same(ll u,ll v)
{
return find(u)==find(v);
}
}s;
struct query
{
ll l,r,k;
query(){}
query(ll _l,ll _r,ll _k)
{
l=_l,r=_r,k=_k;
}
}q[MAXN];
ll a[MAXN];
ll cnt=0;
void disc()
{
std::sort(a+1,a+cnt+1);
cnt=std::unique(a+1,a+cnt+1)-(a+1);
}
ll place(ll x)
{
return std::lower_bound(a+1,a+cnt+1,x)-a;
}
int main()
{
ll n=read(),m=read();
for(ll i=1;i<=m;++i)
{
ll l=read()-1,r=read();
char c=getchar();
while(c!='e'&&c!='o')c=getchar();
q[i]=query(l,r,c=='o');
a[++cnt]=l,a[++cnt]=r;
}
disc();
s.build(cnt<<1);//[1,cnt]:x_even;[cnt+1,2cnt]:x_odd
for(ll i=1;i<=m;++i)
{
ll l=place(q[i].l),r=place(q[i].r),k=q[i].k;
ll l_even=l,l_odd=l+cnt,r_even=r,r_odd=r+cnt;
if(!k)
{
if(s.same(l_odd,r_even)||s.same(l_even,r_odd))
{
printf("%lld\n",i-1);
return 0;
}
else s.uni(l_odd,r_odd),s.uni(l_even,r_even);
}
else
{
if(s.same(l_even,r_even)||s.same(l_odd,r_odd))
{
printf("%lld\n",i-1);
return 0;
}
else s.uni(l_even,r_odd),s.uni(l_odd,r_even);
}
}
printf("%lld",m);
return 0;
}