第十三届蓝桥杯JavaA组、C++A组省赛 J 题——推导部分和 (AC)

1.推导部分和

1.题目描述

对于一个长度为 $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_{l_i}+A_{l_i+1}+\cdots +A_{r_i}$, 值是 $S_i$。

2.输入格式

第一行包含 3 个整数 $N、M$ 和 $Q$ 。分别代表数组长度、已知的部分和数量 和询问的部分和数量。

接下来 $M$ 行, 每行包含 3 个整数 $l_i,r_i,S_i$ 。接下来 $Q$ 行, 每行包含 2 个整数 $l$ 和 $r$, 代表一个小蓝想知道的部分和。

3.输入格式

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

4.样例输入

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

5.样例输出

15
6
UNKNOWN

6.数据范围

对于所有评测用例, $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,$ 。数据保证没有矛盾。

7.原题链接

推导部分和

2.解题思路

  首先先考虑我们平时在前缀和数组中如何求解一段区间 $[l,r]$的和，我们一般是写为$s[r]-s[l-1]$。如果已知区间 $[l,r]$ 的和，这意味着我们可以从 $l-1$ 跳转到 $r$。

  如图，假设给定区间$[2,4]$和$[5,7]$的和，很明显两个区间结合起来我们可以得到$[2,7]$的和。我们一段已知区间$[l,r]$，我们将 $l-1$ 和 $r$ 连通起来，如图红线。可知$1、4、7$处于一个连通分量，这意味着我们可以通过$s[7]-s[4]$来得到区间$[5,7]$的和以及$s[4]-s[1]$来得到$[2,4]$的和，最主要的是可以通过$s[7]-s[1]$来得到$[2,7]$的和，由此可以产生合并效果。

  维护连通分量我们理所应当使用并查集来维护，当求解区间$[l,r]$的值时，我们只需要判断 $l-1$ 和 $r$ 是否属于同一个连通分量即可，如果不是则说明无解输出UNKNOWN。当然题目需要我们输出具体的区间和而不是判断是否能求解出，所以朴素的并查集并无法满足我们的要求，我们需要使用带权并查集。

  不熟悉带权并查集的同学请回顾前文：带权并查集

  我们同样来维护到头结点的距离，而头结点应当是每个联通分量最右端的点，如果上图点 4 到 点 7 的距离就是 $[5,7]$ 区间和，而点 1 到 点 4 的距离同理可维护。因为 7 才应该是头结点，所以 1 到 7 的距离应当是 1 到 4 加上 4 到 7，这在并查集路径压缩中可实现。求解区间$[l,r]$ 时，只需要用 $d[r]-d[l-1]$ 即可，d[]则是维护联通分量中到头结点的距离，具体细节见代码。

3.Ac_code

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) (int)s.size();
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

struct UF {
    std::vector<LL> f, d;
    UF(int n) : f(n), d(n, 0) { std::iota(f.begin(), f.end(), 0); }
    int find(int x) {
        if (x == f[x]) return x;
        //先记录祖宗
        int root = find(f[x]);
        //加上父亲的距离
        d[x] += d[f[x]];
        return f[x] = root;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int u, int v, LL w) {
        int x = find(u);
        int y = find(v);
        if (x == y) return false;
        f[x] = y;
        d[x] = w + d[v] - d[u];
        return true;
    }
};
int n, m, q;
LL s;
void solve()
{
    cin >> n >> m >> q;
    UF uf(n + 10);
    for (int i = 1; i <= m; ++i)
    {
        LL l, r , s;
        cin >> l >> r >> s;
        uf.merge(l - 1, r , s);
    }
    for (int i = 1; i <= q; ++i)
    {
        int l, r;
        cin>>l>>r;
        if (!uf.same(l - 1, r)) cout << "UNKNOWN" << '\n';
        else cout << uf.d[l - 1] - uf.d[r] << '\n';
    }
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65