第十三届蓝桥杯省赛A组题解传送门

题目大意

对于一个长度为$n$的数组$a$
现在知道$m$个部分和
处理$q$个询问，每个询问给出$l,r$，问$[l,r]$这段区间的和是什么

解题思路

转换成一个图论的问题
每告诉一个部分和$s[r]-s[l-1]=v$
相当于由$l-1$向$r$单向连一条权值为$v$的边，$r$向$l-1$单向连一条权值为$-v$的边
然后我们只要去$bfs$
对于每一个连通块内部，记根结点的$s[root]=0$(甚至你随便设一个数也可以)
然后我们就可以根据之前构建的边，处理出这块连通块里所有点到根节点的距离
那么此时，如果我们遇到一组询问，问$[l,r]$的区间和
我们只需要回答$(s[r]-s[root])-(s[l-1]-s[root])$
那么其实就是$s[r]-s[l-1]$(所以$s[root]$的值可以随便设)
然后什么时候$Unknown$呢？
当$r$和$l-1$不在同一连通块时，显然推导不出这段部分和
所以用并查集快速判断两点是否处于同一连通块即可
$PS$:当然也可以用带权并查集，会快很多，但是这个写法会好理解一点

具体代码

#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<int, LL> PIL;
const int N = 2e5 + 10;
int n, m, q;
int p[N]; //并查集只起到一个“检查两点是否处于同一连通块”的作用
LL s[N];
std::vector<PIL> e[N];
bool st[N];
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
void bfs(int root) //这相当于是这块连通块的起点，放在数轴上就是最左边的数
{
    std::queue<int> q;
    q.push(root);
    st[root] = true;
    s[root] = 114514; //随便取什么值，只要别太大导致溢出就可以
    while (q.size())
    {
        auto u = q.front();
        q.pop();
        for (auto v : e[u])
        {
            if (st[v.first])
                continue;
            st[v.first] = true;
            s[v.first] = s[u] + v.second;
            q.push(v.first);
        }
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n >> m >> q;
    for (int i = 0; i <= n; ++i)
        p[i] = i;
    for (int i = 1; i <= m; ++i)
    {
        int l, r;
        LL v;
        std::cin >> l >> r >> v;
        e[l - 1].push_back({r, v});
        e[r].push_back({l - 1, -v});
        p[find(l - 1)] = find(r);
    }
    for (int i = 0; i <= n; ++i)
        if (!st[i]) //新的连通块
            bfs(i);
    for (int i = 1; i <= q; ++i)
    {
        int l, r;
        std::cin >> l >> r;
        if (find(l - 1) != find(r))
            std::cout << "UNKNOWN" << '\n';
        else
            std::cout << s[r] - s[l - 1] << '\n';
    }
    return 0;
}