⭐️前面的话⭐️

【2022年蓝桥杯真题之带权并查集问题】推导部分和
对于一个长度为 $N$ 的整数数列 $A_1,A_2,\cdots A_N$, 小蓝想知道下标 $l$ 到 $r$ 的部分和 ${\sum }_{i=l}^r=A_l+A_{l+1}+\cdots +A_r$ 是多少?
然而, 小蓝并不知道数列中每个数的值是多少, 他只知道它的 $M$ 个部 分和的值。其中第 $i$ 个部分和是下标 $l_i$ 到 $r_i$ 的部分和 ${\sum }_{j=l_i}^{r_i}=$ $A_{li}+A_{li+1}+\cdots +A_{ri}$, 值是 $S_i$ 。解题代码：Java, C++。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2023年3月20日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

📌导航小助手📌

• ⭐️推导部分和⭐️
• • 🔐题目详情
  • • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 评测用例规模与约定
    • 运行限制
  • 💡解题思路
  • 🔑源代码
• 🌱总结

---

⭐️推导部分和⭐️

🔐题目详情

问题描述

对于一个长度为 $N$ 的整数数列 $A_1,A_2,\cdots A_N$, 小蓝想知道下标 $l$ 到 $r$ 的部分和 ${\sum }_{i=l}^r=A_l+A_{l+1}+\cdots +A_r$ 是多少?
然而, 小蓝并不知道数列中每个数的值是多少, 他只知道它的 $M$ 个部 分和的值。其中第 $i$ 个部分和是下标 $l_i$ 到 $r_i$ 的部分和 ${\sum }_{j=l_i}^{r_i}=$ $A_{li}+A_{li+1}+\cdots +A_{ri}$, 值是 $S_i$ 。

输入格式

第一行包含 3 个整数 $N、M$ 和 $Q$ 。分别代表数组长度、已知的部 分和数量和询问的部分和数量。
接下来 $M$ 行, 每行包含 3 个整数 $l_i,r_i,S_i$ 。
接下来 $Q$ 行, 每行包含 2 个整数 $l$ 和 $r$, 代表一个小蓝想知道的部分 和。

输出格式

对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 UNKNOWN。

样例输入

5 3 3
1 5 15
4 5 9
2 3 5
1 5
1 3
1 2

样例输出

15
6
UNKNOWN

评测用例规模与约定

对于 $10\%$ 的评测用例, $1\le N,M,Q\le 10,-100\le S_i\le 100$
对于 $20\%$ 的评测用例, $1\le N,M,Q\le 20,-1000\le S_i\le 1000$
对于 $30\%$ 的评测用例, $1\le N,M,Q\le 50,-10000\le S_i\le$ 10000 。
对于 $40\%$ 的评测用例, $1\le N,M,Q\le 1000,-10^6\le S_i\le 10^6$
对于 $60\%$ 的评测用例, $1\le N,M,Q\le 10000,-10^9\le S_i\le$ $10^9$ 。
对于所有评测用例, $1\le N,M,Q\le 10^5,-10^{12}\le S_i\le$ $10^{12},1\le l_i\le r_i\le N,1\le l\le r\le N$ 。数据保证没有矛盾。

运行限制

• 最大运行时间：3s
• 最大运行内存: 512M

💡解题思路

根据前缀和的经验，我们知道区间$[l,r]$的和可以表示为$d[r]-d[l-1]$，其中$d$为前缀和数组，这道题差不多是反着过来的，题目会给定若干组区间和，然后需要根据这些信息去推导其他区间的区间和，第一眼看了是完全懵逼的，看了一位大佬的题解后【大佬贴贴】，明白可以使用带权并查集来做，这个和y总讲的算法基础课中的【食物链】这道题有点像。

前缀和是第一个元素为参照，陆续求出后续元素的累加和，利用区间相减的原则推导出某段区间的和。使用带权并查集来做可以类比一下，我们以并查集的根节点为参照，如$d[r]$就表示$r$结点到所在并查集的距离，同理对于$[l,r]$的区间和也可以使用$d[r]-d[l-1]$来表示。假设区间$[l,r]$的区间和为$s$，由于$[l,r]$区间和表示为$d[r]-d[l-1]$，也就是$r$到根的距离与$l-1$到根的距离之差，我们可以将$r$所在并查集和$l-1$所在并查集进行合并，为了方便表示不妨记录$t=l-1$。

合并前：$s=d[r]-d[t]$

合并后：$s=d[r]-(d[t]+d[pt])$
$d[pt]=d[r]-d[t]-s$

将所有区间全部加入并查集后就可以直接利用类似前缀和的写法进行查询。

在查询时，如果$l-1$与$r$不在同一个并查集当中，那么肯定是求不出来了，否则可以查询到结果。

🔑源代码

并查集实现时利用路径压缩增加效率。

java 代码：

import java.util.*;

class Main {
    static final int N = (int) 2e5 + 10;
    
    static int[] p = new int[N];
    static long[] d = new long[N];
    
    static Scanner sc = new Scanner(System.in);
    static int n, m, q;
    
    static int find(int x) {
        if (p[x] != x) {
            int t = p[x];
            p[x] = find(p[x]);
            d[x] += d[t];
        }   
        return p[x];
    }
    
    public static void main(String[] args) {
        n = sc.nextInt();
        m = sc.nextInt();
        q = sc.nextInt();
        
        //init uf
        for (int i = 1; i <= n; i++) p[i] = i;
        
        while (m-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            long s = sc.nextLong();
            int pt = find(l - 1), pr = find(r);
            p[pt] = pr;
            //更新d[pt]
            d[pt] = d[r] - s - d[l - 1];
        }
        
        while (q-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            
            int pt = find(l - 1), pr = find(r);
            if (pt != pr) System.out.println("UNKNOWN");
            else System.out.println(d[r] - d[l - 1]);
        }
    }
}

c++代码：

//带权并查集 与算法基础课中的食物链较像
//以一个根结点为参照，l-1到根结点的距离为d[l-1] r到根结点的距离为d[r]
//根据前缀和原理 [l, r] 区间和为 d[r] - d[l - 1]
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = (int) 2e5 + 10;

//并查集 
int p[N];
//到根的权重
LL d[N];

int n, m, q;

int find(int x) 
{
    if (p[x] != x) 
    {
        int t = p[x];
        p[x] = find(p[x]);
        d[x] += d[t];
    }
    return p[x];
}

int main() 
{
    cin >> n >> m >> q;
    //初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i;
    while (m-- > 0) 
    {
        LL l, r, s;
        cin >> l >> r >> s;
        
        //找根结点
        int pl = find(l - 1), pr = find(r);
        //合并
        p[pl] = pr;
        d[pl] = d[r] - d[l - 1] - s;
    }
    
    //查询
    //如果l, r都在同一个集合，则存在结果，否则不能查出结果
    while (q-- > 0) 
    {
        int l, r;
        
        cin >> l >> r;
        int pl = find(l - 1), pr = find(r);
        
        if (pl != pr) cout << "UNKNOWN" << endl;
        else cout << d[r] - d[l - 1] << endl;
    }
    
    return 0;
}

🌱总结

本题思维难度较大，带权并查集的思路并不好想。

---

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！