P8779题解

千早爱音 · 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';
    }
}