目录
问题概述
这里给出两个题目，一个是上一篇的新春漫步(其实当时给的官方题解就是链式并查集的写法，但是当时我懒得写了，emmm)，二是最近vp的一场cf_div3_923场的d题，准确来说，就是因为这个我才准备写这个的，题目大概就是给出一个长度为n的数组和q组询问，每组询问会给出左区间和右区间，要求判断该区间内的数值是否一致，如果一样输出"-1 -1"，否则输出一组属于该区间的不同元素的索引坐标，原题参考D. Find the Different Ones!
思路分析
首先，我们看一下这两个题的共同之处在哪里，对于"新春漫步"，在上一篇随便里也写到，其实它的逻辑从出发位置找到第一个不为0的元素，其间的元素应该都是0，也就是说，是连续的；同样的，这个cf的题目，也是在一个区间内找到两个不同的元素，我们简单分析一下，对于一个位置，我们记录第一个和他不同的元素的位置，将这个位置与给出的右区间进行对比，是否就可以得出给出的区间是否是一致的的这个问题，也就是说，对于给出数组的每一个元素，我们记录向右的第一个和他不同的值即可，同样的，新春漫步也是维护这个值而已
参考代码
- 新春漫步
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 1e6+7;
int a[N];
//题目显示大量读写
inline int read() {
//使用快读记得别关流 会tle的
int res = 0, mark = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') mark = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
res = (res<<1) + (res<<3) + (ch^48);
ch = getchar();
}
return res * mark;
}
inline void write(int x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) write(x/10);
putchar(x%10 + '0');
}
struct DSU {
int fa[1000007];
//并查集，支持查找、合并、计数操作（最后剩余多少集合）
DSU(int n) {
for(int i=1; i<=n; i++) fa[i] = i;
fa[n+1] = 0;
}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void us(int x, int y) {
fa[find(x)] = find(y);
}
};
void solve() {
int n, m;
n = read(), m = read();
DSU k(n);
//最初每个点可以到达的最远的位置就是自己，题目给出了每个点最开始都有障碍物，如果没有的话，那么就要再多一遍由后向前的遍历
for(int i=1; i<=n; i++) a[i] = read();
while(m --) {
int op, x, y;
op = read(), x = read();
if(op == 1) {
y = read();
if(a[x] > 0) {
a[x] -= y;
//如果当前位置的障碍物消失，那么可以到达最远的位置就是右边元素可以到达最远的位置
//当然，作为最后一位是不需要更改的，否则就会出现fa[i] = 0的情况
if(x < n && a[x] <= 0) k.fa[x] = k.find(x+1);
}
}
else {
write(k.find(x));
putchar('\n');
}
}
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
//FAST_IO;
int t = 1;
//t = read();
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
- Find the Different Ones!
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 2e5+7;
int n, q, a[N];
struct DSU {
int fa[200007];
//并查集，支持查找、合并、计数操作（最后剩余多少集合）
DSU(int n) {for(int i=1; i<=n; i++) fa[i] = i;}
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void us(int x, int y) {
fa[find(x)] = find(y);
}
};
void solve() {
cin >> n;
DSU k(n);
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=n; i>=1; i--) {
//这里就是上面说的由后向前初始预处理一次
if(a[i] == a[i+1]) k.fa[i] = k.fa[i+1];
}
cin >> q;
while(q --) {
int x, y;
cin >> x >> y;
//如果当前点的祖先的位置超过右区间的位置，说明没有不同元素，否则，输出最近的不同的元素位置
if(k.find(x) >= y) cout << -1 << " " << -1 << endl;
else cout << x << " " << k.fa[x]+1 << endl;
}
cout << endl;
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
FAST_IO;
int t = 1;
cin >> t;
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
做题总结
区间的连续性问题，用链式并查集可以做到O(n)的时间复杂度，而且空间复杂度也不高，编码也简单，相较于线段树、树状数组等，用起来舒服很多，不过要想想明白逻辑，也满足就是连续性这个特点，这也是链的特点，假如链都不连续，怎么叫链呢