<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
问题描述具有一定误导性,另外对于权值的含义,原帖并未提及,对此两点不足,本帖统一补充
并查集
先来解决第一个,关于误导性的问题:为什么给出的是区间信息,却不能用线段树或者树状数组?
o代表odd奇数,e代表even偶数,假设两条黑实线段代表已经确定了的关系,红实线段代表即将被确定的关系,由于区间上1的分布可能不是连续均匀的,出现这种情况,黑虚线段上,以及红黑实线段相交的部分中,1的数量是奇数还是偶数,都是无法确定的,构造节点的时候不方便了
但是,树状数组中的前缀和思想可以用在这里,用$S_i$表示$[0,i]$区间上1的个数,那么$[l,r]$上1的个数就等于$S_r-S_{l-1}$,$[l,r]$区间上1的个数为偶数就代表着$S_r$和$S_{l-1}$奇偶性相同,反之则不同,问题转化为对2*m个元素的二分类问题,分类对象是所有的$S_i$
由于m条指令最多包含2*m个元素,不一定能覆盖整个序列(长度最大值为$10^9$),因此要借助哈希表来离散化
接下来就是第二个问题:权值如何生成,代表什么?
对于m条指令,每条中的odd,even代表着l-1和r是异类或同类,每出现一条,就判断当前指令有无违反此前的分类方式,没有违反就尝试分类,对于给出的两个元素,在并查集中合并的同时,如果同类就赋予权值0,异类则赋予权值1,奇偶性是否相同只要判断模2之后的值是否相等。合并的时候如果元素本身带有权值,需要按照下图方式合并:
并查集中的一个集合到对应源的权值和,与它通向源的路径无关,mod表示权值,合并操作默认将l合并到r上,如果l,r的源分别是pr,nx,则pr合并到nx上的时候,权值需要增加$mod[r]+t-mod[l]$,但由于模2,在代码中写成了全加,因此没有影响
细节请见注释
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
//mod记录每个元素和对应源之间的权值和对2(分类数)取模的值
vector<int> mod, ori;
//以下用于离散化
int m, tot = 1;
unordered_map<int, int> idx;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//取得离散化后的索引
auto getIndex = [=](int x) {
if (idx.find(x) == idx.end()) idx[x] = tot++;
return idx[x];
};
//查找源节点,并合并路径上的权值
function<int(int)> find = [&find](int x)->int {
if (x != ori[x]) {
int o = find(ori[x]);
//路径压缩的时候一并累加权值(取模可以现在取,也可以之后判断的时候取)
mod[x] += mod[ori[x]];
ori[x] = o;
}
return ori[x];
};
//既然要离散化,那n实际上是无意义的
cin >> m >> m;
int ans = m;
//离散化后最多产生2*m个元素,前缀和s[0]=0也需要存储
ori.resize(2 * m + 1);
mod.resize(2 * m + 1);
iota(ori.begin(), ori.end(), 0);
for (int i = 1; i <= m; i++) {
int l, r;
string oe;
cin >> l >> r >> oe;
//按照前缀和思想,转化为对应索引
l = getIndex(l - 1);
r = getIndex(r);
//字符串oe是"odd"还是"even"实际上就代表了l和r是不同类还是同类
int t = (oe == "odd") ? 1 : 0,
pr = find(l), nx = find(r);
//pr==nx就代表着两者已经同属一个集合,就是关系已经确定
if (pr == nx) {
//取模后相等即同类,不相等则不同类
if (((t == 1) && (mod[l] % 2 == mod[r] % 2))
|| ((t == 0) && (mod[l] % 2 != mod[r] % 2))) {
//if的条件就是“本该同类却被告知不同类,或本该不同类却被告知同类”
ans = i - 1;
break;
}
}
else {
//关系无法确定,那就当场确定它们的关系(合并)
ori[pr] = nx;
//真值应该是mod[r]+t-mod[l],但取模后没有影响
mod[pr] = (mod[l] + mod[r] + t) % 2;
}
}
cout << ans << endl;
return 0;
}