以一道区间和查询来说明板子如何使用

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;
}