题意:
一个长度为$n$的$01$序列,给定$m$个区间,每次告诉区间内$1$的数量。从实际角度出发考虑这些区间内$1$的数量可能不是正确的,问从第$1$次给定的区间开始,第$k$次前给定区间的$1$的数量是正确的。
数据范围:$1\leq n\leq 10^9, 1\leq m\leq 10000$
题解:
考虑给定一个区间,则这个区间内的$1$的数量可以由$d[l-1]$和$d[r]$两者来表示。
当$d[r] - d[l - 1]$为奇数,则说明$[l,r]$内的$1$的个数为奇数,否则为偶数。
那么之后判断一区间内数的个数为奇偶时,可以通过其共同祖先来判断。
如:$[1,3]$内$1$的个数为奇数,$[3,7]$内$1$的个数为奇数,则$[1,7]$内$1$的个数为奇偶的判断为:
$1$的祖先为$3$,$d[3] - d[0] =\ $奇数
$7$的祖先为$3$,$d[7] - d[3] =\ $奇数
则$d[7] - d[0] = (d[7] - d[3]) + (d[3] - d[0]) =\ $偶数
那么这样就可以每次通过计算出$a$和$b$的祖先$pb$之间$1$的个数,再得到$b$和$pb$之间$1$的个数即可得到两者之间数的个数。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 20010;
int n, m;
int p[N], d[N];
unordered_map<int, int> mp;
char type[10];
int a, b;
//离散化得到相对大小的位置
int get(int x) {
if(!mp.count(x)) mp[x] = ++n;
return mp[x];
}
int find(int x) {
if(x != p[x]) {
int rt = find(p[x]);
d[x] ^= d[p[x]];
p[x] = rt;
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
n = 0;
for(int i = 0; i < N; ++i) p[i] = i;
int res = m;
for(int i = 1; i <= m; ++i) {
scanf("%d%d%s", &a, &b, type);
//获取当前的相对索引
a = get(a - 1), b = get(b);
//判断一下当前读入的区间中给定的是奇数个1还是偶数个1
int t = 0;
if(*type == 'o') t = 1;
//找到其祖先,看其是否已经知道了互相之间的关系
int pa = find(a), pb = find(b);
//如果知道了就判断下两者已经确定的关系和当前给定的关系是否冲突
if(pa == pb) {
if((d[a] ^ d[b]) != t) {
res = i - 1;
break;
}
}
//如果不知道就合并两者,从a的根pa到b的根pb之间的关系为给定关系减去a到pa,b到pb之和
else {
p[pa] = pb;
d[pa] = d[a] ^ d[b] ^ t;
}
}
printf("%d\n", res);
return 0;
}