poj1733(带权并查集+离散化)

时间:2021-09-03 09:29:27

题目链接:http://poj.org/problem?id=1733

题意:给定由0、1组成的数串长度n,询问次数m,每次询问给出a,b,s,表示区间[a,b]内1的数量为s(odd-奇数或even-偶数),求前几次询问的答案是正确的。

思路:此题类似与poj1182,属于并查集的向量应用。首先n<=1e9,必须要用到离散化,这里用map实现,详见代码。然后要用到带权并查集,用1表示odd,0表示even。用root[i]表示i的祖先r,f[i]表示[r,i)(左闭右开,所以输入的b要加一)之间1的个数(偶数用0表示,奇数用1表示),且(x->z)=(x->y)^(y->z)。每次查询若有相同的祖先(ra=rb),则判断是否满足(b->a)^(a->ra)==(b->rb),若不是则代表当前答案有问题,退出循环; 若祖先不同,则合并,并更新祖先rb到新祖先ra的f[rb]的值,f[rb]=(c^f[b])^f[a]。(不懂的话自己手动算一下,简单的向量运算)。

AC代码:

 #include<cstdio>
#include<map>
using namespace std; const int maxn=;
int n,m,cnt,root[maxn],f[maxn];
map<int,int> mp; int getr(int k){
if(root[k]==k) return k;
else{
int tmp=root[k];
root[k]=getr(root[k]);
f[k]^=f[tmp];
return root[k];
}
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=maxn;++i)
root[i]=i,f[i]=;
int p;
for(p=;p<=m;++p){
int a,b,c,ra,rb;
char s[];
scanf("%d%d%s",&a,&b,s);
if(s[]=='e') c=;
else c=;
++b;
if(!mp.count(a))
mp[a]=++cnt;
if(!mp.count(b))
mp[b]=++cnt;
a=mp[a],b=mp[b];
ra=getr(a),rb=getr(b);
if(ra==rb){
if(c^f[a]!=f[b])
break;
}
else{
root[rb]=ra;
f[rb]=(c^f[b])^f[a];
}
}
printf("%d\n",p-);
return ;
}