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

柔情只为你懂 2023-09-28 23:22 64阅读 0赞

#### 目录 ####

*  1.推导部分和
 *   *  1.题目描述
     *  2.输入格式
     *  3.输入格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3.Ac\_code

## 1.推导部分和 ##

### 1.题目描述 ###

对于一个长度为  N N N 的整数数列  A 1 , A 2 , ⋯ A N A\_\{1\}, A\_\{2\}, \\cdots A\_\{N\} A1,A2,⋯AN , 小蓝想知道下标  l l l 到  r r r 的部分和  ∑ i = l r = A l + A l + 1 + ⋯ + A r \\sum\_\{i=l\}^\{r\}=A\_\{l\}+A\_\{l+1\}+\\cdots+A\_\{r\} ∑i=lr=Al\+Al\+1\+⋯\+Ar是多少?

然而, 小蓝并不知道数列中每个数的值是多少, 他只知道它的  M M M 个部分和 的值。  
其中第  i i i 个部分和是下标  l i l\_\{i\} li到  r i r\_\{i\} ri 的部分和  ∑ j = l i r i = A l i + A l i + 1 + ⋯ + A r i \\sum\_\{j=l\_\{i\}\}^\{r\_\{i\}\}=A\_\{l\_\{i\}\}+A\_\{l\_\{i\}+1\}+\\cdots+A\_\{r\_\{i\}\} ∑j=liri=Ali\+Ali\+1\+⋯\+Ari, 值是  S i S\_\{i\} Si。

### 2.输入格式 ###

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

接下来  M M M 行, 每行包含 3 个整数  l i , r i , S i l\_\{i\}, r\_\{i\}, S\_\{i\} li,ri,Si 。接下来  Q Q Q 行, 每行包含 2 个整数  l l l 和  r r 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 ≤ N , M , Q ≤ 1 0 5 , − 1 0 12 ≤ S i ≤ 1 0 12 , 1 ≤ l i ≤ r i ≤ N ， 1 ≤ l ≤ r ≤ N , 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≤ l ≤ r ≤ N, 1≤N,M,Q≤105,−1012≤Si≤1012,1≤li≤ri≤N，1≤l≤r≤N, 。数据保证没有矛盾。

### 7.原题链接 ###

[推导部分和][Link 1]

## 2.解题思路 ##

首先先考虑我们平时在前缀和数组中如何求解一段区间  \[ l , r \] \[l,r\] \[l,r\]的和，我们一般是写为 s \[ r \] − s \[ l − 1 \] s\[r\]-s\[l-1\] s\[r\]−s\[l−1\]。如果已知区间  \[ l , r \] \[l,r\] \[l,r\] 的和，这意味着我们可以从  l − 1 l-1 l−1 跳转到  r r r。  
![在这里插入图片描述][b1ca4cddda8a4596b8dabe820f09e4f4.png]  
  如图，假设给定区间 \[ 2 , 4 \] \[2,4\] \[2,4\]和 \[ 5 , 7 \] \[5,7\] \[5,7\]的和，很明显两个区间结合起来我们可以得到 \[ 2 , 7 \] \[2,7\] \[2,7\]的和。我们一段已知区间 \[ l , r \] \[l,r\] \[l,r\]，我们将  l − 1 l-1 l−1 和  r r r 连通起来，如图红线。可知 1 、 4 、 7 1、4、7 1、4、7处于一个连通分量，这意味着我们可以通过 s \[ 7 \] − s \[ 4 \] s\[7\]-s\[4\] s\[7\]−s\[4\]来得到区间 \[ 5 , 7 \] \[5,7\] \[5,7\]的和以及 s \[ 4 \] − s \[ 1 \] s\[4\]-s\[1\] s\[4\]−s\[1\]来得到 \[ 2 , 4 \] \[2,4\] \[2,4\]的和，最主要的是可以通过 s \[ 7 \] − s \[ 1 \] s\[7\]-s\[1\] s\[7\]−s\[1\]来得到 \[ 2 , 7 \] \[2,7\] \[2,7\]的和，由此可以产生合并效果。

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

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

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

## 3.Ac\_code ##

#include<bits/stdc++.h>
    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;
    }

[Link 1]: https://blog.csdn.net/m0_57487901/article/details/127286301?spm=1001.2014.3001.5502
[b1ca4cddda8a4596b8dabe820f09e4f4.png]: https://img-blog.csdnimg.cn/b1ca4cddda8a4596b8dabe820f09e4f4.png
[Link 2]: http://t.csdn.cn/XlGKf