Parity
1003. Parity @ Timus Online Judge
一个 $01$ 序列。
大意就是给你一些区间的奇偶性，然后你要找到最早在哪个区间出了问题。
这个题目首先要把区间改成左闭右开，然后离散化一下，最后用带权并查集维护一下就行了，关于奇偶性的转移全部用带权并查集维护即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include<cstring>
#include<algorithm>
#define N 510000
using namespace std;
int l[N],r[N],type[N];
struct node
{
int *x;int val;
}a[N];int top;
inline bool cmp(node x,node y){return x.val<y.val;}
int n,m;
int fa[N],val[N];
inline int findfa(int x)
{
if(x==fa[x])return x;
int y=findfa(fa[x]);val[x]^=val[fa[x]];fa[x]=y;
return y;
}
inline void mer(int x,int y,int type)
{
if(x>y)x^=y^=x^=y;
fa[y]=x;val[y]=type;
}
char st[100];
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==-1)break;
n++;
scanf("%d",&m);
top=0;
int ans=m+1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l[i],&r[i]);r[i]++;
scanf("%s",st+1);
if((l[i]<1 || r[i]>n || l[i]>r[i]) && ans==m+1)
{
ans=i;
break;
}
if(st[1]=='e')type[i]=0;
else type[i]=1;
a[++top].x=&l[i];a[top].val=l[i];
a[++top].x=&r[i];a[top].val=r[i];
}
if(ans!=m+1)
{
printf("%d\n",ans-1);
continue;
}
sort(a+1,a+top+1,cmp);
if(top>=1)(*a[1].x)=1;
for(int i=2;i<=top;i++)
{
if(a[i].val==a[i-1].val)(*a[i].x)=(*a[i-1].x);
else (*a[i].x)=(*a[i-1].x)+1;
}
if(top>=1)n=(*a[top].x);
for(int i=1;i<=n;i++)fa[i]=i,val[i]=0;
for(int i=1;i<=m;i++)
{
int tx=findfa(l[i]),ty=findfa(r[i]);
if(tx==ty)
{
if((val[l[i]]^val[r[i]])!=type[i])
{
ans=i;
break;
}
}
else mer(tx,ty,val[l[i]]^val[r[i]]^type[i]);
}
printf("%d\n",ans-1);
}
return 0;
}
|
虽然会做，但是我一直在冥思苦想为什么正确，比如：$[1,3],[3,4]$ 虽然并查集上无关，但都包含 $3$ ，总归有点关系，且在并查集上，只有当左闭右开区间有个端点重合时，在并查集上才有关联，但是有没有可能一坨区间有些端点重合，有些不重合，然后解出了并查集不能处理出奇偶性区间的奇偶性。（简单来说就是我找不到一种合适的解释或者较为严谨的证明去解释这个并查集做法，因为区间之间的关联性错综复杂）
但是后来翻资料发现了一种合适的解释：
其实可以对数组进行异或前缀和 $f$ ，那么对于区间 $[a,b)$ ，我们就能得到 $f[a]$ 和 $f[b]$ 的关系，仔细想想 $(a,b)$ 之间的 $c$ 的 $f$ 会不会受到 $a,b$ 的影响呢？事实上并不会，因为 $f[c]$ 不管取什么，最后只要从后往前再做一遍前缀和就可以得到原数组（即原数组存在与否与 $f[c]$ 取值无关），即 $f[c]$ 的取值与 $f[a],f[b]$ 无关。
类似的，即使 $f[c]$ 与 $f[d]$ 有关系，这个关系与 $a,b$ 也没有关系，因为 $f[c]$ 的取值与 $f[a],f[b]$ 无关。
总的来讲，这样问题就不是一个区间了，而是只涉及到了点的关系，就非常好考虑了。（区间的错综复杂考虑起来真的好恶心QAQ）
综上，在做 $01$ 异或型区间问题的时候，前缀和可以帮助我们把区间问题变成点值问题来考虑，思考难度就下降不少了。
