1. 2030: [蓝桥杯2022初赛] 推导部分和

传送门：http://oj.ecustacm.cn/problem.php?id=2030

1.1. 题意

对于数列$a$，已知部分区间和，询问若干次区间和。

1.2. Tag

并查集、搜索

1.3. 难度

☆☆☆☆

1.4. 思路

对于已知的区间$[l,r]$的和为$s$，用前缀和$sum[r]-sum[l-1]=s$表示，根据差分约束建图准则，相当于点$l-1$到点$r$长度为$s$，$r$到$l-1$长度为$-s$。

建好图之后，每次询问一个区间$[ql,qr]$的和，相当于询问$sum[qr]-sum[ql-1]$的值。

首先要保证$ql-1$和$qr$在同一个连通块中，其次每个连通块只需要随便一个点初始化为$0$，然后按照边长扩展即可。这是由于等号，不管怎么走，相对差值是不变的。

代码中$dfs$和$bfs$均可以。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x = x * w;
}
const int maxn = 1e5 + 10;
const ll INF = -1e13;
int n, m, q;
struct edge{
    int v; ll w;
    edge(){}
    edge(int v, ll w):v(v), w(w){}
};
vector<edge>Map[maxn];
ll sum[maxn];
bool vis[maxn];
void dfs(int u, ll d){
    vis[u] = 1;
    sum[u] = d;
    ///cout<<u<<" "<<d<<endl;
    for(auto x : Map[u])
    {
        int v = x.v; ll w = x.w;
        if(vis[v])continue;
        dfs(v, d + w);
    }
}
queue<pair<int,ll> >Q;
void bfs(int u, ll d){
    vis[u] = 1;
    sum[u] = d;
    Q.push(make_pair(u, d));
    while(!Q.empty())
    {
        auto now = Q.front();
        Q.pop();
        int u = now.first; ll d = now.second;
        for(auto x : Map[u])
        {
            int v = x.v; ll w = x.w;
            if(vis[v])continue;
            vis[v] = 1;
            sum[v] = d + w;
            Q.push(make_pair(v, d + w));
        }
    }
}
int f[maxn];
int Find(int x){
    return x == f[x] ? x : f[x] = Find(f[x]);
}
int main(){
    read(n);read(m);read(q);
    for(int i = 0; i <= n; i++)f[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int l, r; ll s;
        read(l);read(r);read(s);
        ///cout<<l<<" "<<r<<" "<<s<<endl;
        ///sum[r] - sum[l - 1] = s
        Map[l - 1].push_back(edge(r, s));
        Map[r].push_back(edge(l - 1, -s));
        f[Find(l - 1)] = Find(r);
    }
    for(int i = 0; i <= n; i++)if(!vis[i])
        bfs(i, 0);
    while(q--)
    {
        int l, r;
        read(l), read(r);
        --l;
        if(Find(l) != Find(r))puts("UNKNOWN");
        else printf("%lld\n", sum[r] - sum[l]);
    }
    return 0;
}