自动搬运

查看原文

来自洛谷，原作者为

	千早爱音 新主页 https://www.luogu.com.cn/paste/3k4tw9fa

搬运于2025-08-24 22:42:24，当前版本为作者最后更新于2022-11-13 13:09:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：P1196 和 ABC238E。不知道为什么两个绿题缝合起来变成黄题了。

首先考虑怎么判断无解的情况。见这篇题解

观察到原数组的具体取值并不重要，我们需要的只是区间 $[l,r]$ 的和为 $sum_r-sum_{l-1}$，其中 $sum$ 代表前缀和。

于是不难想到一个思路：对于给定的一个区间 $[l,r]$，建无向边 $(l-1,r)$，代表由 $sum_r$ 的信息能推出 $sum_{l-1}$ 的信息，反之亦然。

于是我们已知 $sum_0=0$，对于一个询问，问题转化为从图上的 $l-1$ 节点能否到达 $r$。这个可以直接用并查集维护。当两个端点不连通则代表无解。

但是现在我们除了知道是否连通之外还需要知道具体的区间和，于是考虑在并查集上维护一个 $val$，表示当前区间到根节点 $0$ 的距离，初始设为 $0$，当合并两个集合时将两个集合对应的 $val$ 值合并即可，则如果当前区间和能被计算出来则区间和为 $val_r-val_{l-1}$。

时间复杂度 $\mathcal{O}(n)$，可以通过。

双倍经验：hdu3038，思路基本是一致的。

代码：

#import <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200000+10;
int n,m,a,b,s;
int par[maxn],val[maxn];
void init(int l,int r)
{
for(int i=l;i<=r;i++) 
par[i]=i,val[i]=0;
}
int find(int x)
{
    if(par[x]==x) 
    return x;
    else
    {
        int root=find(par[x]);
        val[x]+=val[par[x]];
        return 
        par[x]=root;
    }
}
signed main()
{
    cin>>n>>m;
    int q;
    cin>>q;
    init(0,n);
    int ans=0;
    for(int i=1,a,b,s;i<=m;i++)
    {
        scanf("%lld%lld%lld",&a,&b,&s); 
        a--;
        int t1=find(a),t2=find(b);
        if(t1!=t2)
        {
            par[t2]=t1;
            val[t2]=-val[b]+s+val[a];
        }
    }
    while(q--)
    {
        scanf("%d%d",&a,&b); 
        a--;
        int t1=find(a),t2=find(b);
        if(t1!=t2)
        cout<<"UNKNOWN\n";
        else
        cout<<val[b]-val[a]<<'\n';
    }
}