【蓝桥杯每日一题】推导部分和—

【蓝桥杯每日一题】推导部分和——带权并查集

推导部分和

2024-12-11 蓝桥杯每日一题推导部分和带权并查集

题目大意

对于一个长度为 ( N ) 的整数数列 ( $A_1, A_2, \cdots, A_N$ )，小蓝想知道下标 ( l ) 到 ( r ) 的部分和 $\sum_{i=l}^r A_i = A_l + A_{l+1} + \cdots + A_r$ 是多少？

然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 ( M ) 个部分和的值。其中第 ( i ) 个部分和是下标 ( $l_i $) 到 ( $r_i $KaTeX parse error: Can't use function '\)' in math mode at position 1: \̲)̲ 的部分和 \($ \sum_{j=l_i}^{r_i} A_j = A_{l_i} + A_{l_i+1} + \cdots + A_{r_i}$，值是 $ S_i $。

解题思路

这个题的思维难度有点大，但是实现来很容易，只要理解带权并查集这一概念即可。

先看这个权值是怎么带上的，d 数组就是代表每一个值到根节点的一个距离，然而当 l 和 r在同一个连通块中的时候，之间的距离就是 d[r] - d[l-1] 的值。

每一个连通块代表着是那些可以通过边界值相连的区间的总和，在合并的过程中会发生如下图的数值变化，如图所示 d[l-1] 的值将会在find函数中通过更新父节点的时候更新成 l-1 到根节点的距离，这时候显然l 和 r 之间的距离就是d[r] - d[l-1]

在这里插入图片描述

Accepted

#include <iostream>

using namespace std;

const int N = 100010;
typedef long long ll;
ll n,m,q;
ll d[N],p[N];

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

int main() {
    cin>>n>>m>>q;
    for(int i = 1;i <= n;i++) p[i] = i;
    ll l,r,s;
    while(m--) {
        cin>>l>>r>>s;

        ll pl = find(l-1),pr = find(r);
        // 直接合并
        p[pl] = pr;
        d[pl] = d[r] - d[l-1] - s;
    }

    while(q--) {
        cin>>l>>r;
        ll pl = find(l-1),pr = find(r);
        if(pl != pr) cout<<"UNKNOWN"<<endl;
        else cout<<d[r] - d[l-1]<<endl;
    }
    return 0;
}