以一道区间和查询来说明板子如何使用
1.merge的时候只需要维护两个根节点的距离，利用的是合并时题目给的信息
2.find的时候更新维护是子节点到根的距离
3.需要加一个查询函数，因为距离数组是开在结构体内部的。
题目描述
对于一个长度为 \(N\) 的整数数列 \(A_{1}, A_{2}, \cdots A_{N}\)，小蓝想知道下标 \(l\) 到 \(r\) 的部分和 \(\sum\limits_{i=l}^{r}A_i=A_{l}+A_{l+1}+\cdots+A_{r}\) 是多少?
然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 \(M\) 个部分和的值。其中第 \(i\) 个部分和是下标 \(l_{i}\) 到 \(r_{i}\) 的部分和 \(\sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}}\), 值是 \(S_{i}\) 。
对于所有评测用例, \(1 \leq N, M, Q \leq 10^{5},-10^{12} \leq S_{i} \leq 10^{12}, 1 \leq l_{i} \leq r_{i} \leq N\), \(1 \leq l \leq r \leq N\) 。数据保证没有矛盾。
蓝桥杯 2022 省赛 A 组 J 题。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define debug1(x) cerr<<x<<" "
#define debug2(x) cerr<<x<<endl
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
struct DSU {
vector<int> f, siz,d;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
d.resize(n);
for(int i=0;i<n;i++)d[i]=0;
}
int find(int x)
{
if (f[x] != x)
{
int root = find(f[x]);
d[x] += d[f[x]];//f[x]到根距离已经被更新
f[x] = root;//让x指向根
}
return f[x];
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int l, int r,int add) {
int x = find(l);
int y = find(r);
if (x == y) {
return false;
}
d[y]=d[l]+add-d[r];
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
int query(int u,int v){
int ans=d[v]-d[u];
return ans;
}
};
void solve(){
int q;
cin>>n>>m>>q;
DSU dsu(n+5);
for(int i=1;i<=m;i++){
int sum=0;
int u,v;cin>>u>>v>>sum;
u--;
dsu.merge(u,v,sum);//根节点是最小值
}
for(int i=1;i<=q;i++){
int u,v;cin>>u>>v;
u--;
if(dsu.same(u,v)){
int ans=dsu.query(u,v);
cout<<ans<<endl;
}
else {
cout<<"UNKNOWN"<<endl;
}
}
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
//cin>>t;
t=1;
while (t--) {
solve();
}
return 0;
}