【题解】[ARC193A] Complement Interval Graph

题意

给你

n

段区间

[l_i,r_i]

，当且仅当

[l_i,r_i]

与

[l_j,r_j]

没有焦点时，

i

和

j

之间有一条无向边。每个点

i

有点权

a_i

，定义一条路径的权值为这条路径上的点权之和，给出若干询问，求出

u

和

v

之间路径权值可能的最小值，若不存在路径，输出

-1

。

思路

设询问的两个点为

x

和

y

，分类讨论一下询问中两个区间的情况：

不相交： $x$ 和 $y$ 之间肯定有一条边，最小可能边权即为 $a_x+a_y$ 。
包含：我们可以认为是从更大的区间走到另一个区间，假设 $[l_x,r_x]$ 是更大的区间，手玩一下可以发现可能的路径必然先跳到不与 $[l_x,r_x]$ 相交的区间，再跳到 $[l_y,r_y]$ 。因为 $x$ 包含了 $y$ ，所以这种路径一定可行，现在我们需要找出与 $[l_x,r_x]$ 不相交的区间中权值最小的那个，也就是说右端点小于 $l_x$ 或者左端点大于 $r_x$ 的区间中权值最小的那个，维护前缀最小和后缀最小即可。
相交，不包含：假设有一个区间 $[l_z,r_z]$ ，其中 $l_z=\min(l_x,l_y)$ ， $r_z=\max(r_x,r_y)$ ，则可以转化为上一种情况。但是在这种情况下还存在另一条可能的路径：从 $x$ 开始，先跳到不与 $x$ 相交且与 $y$ 相交的区间，再跳到与 $x$ 相交且与 $y$ 不相交的区间，最终跳到区间 $y$ 。这条路径可能的最小权值为 $a_x+a_y$ 再加上右端点在 $\max(l_x,l_y)$ 左边的区间的权值与左端点在 $\min(r_x,r_y)$ 右边的区间的权值（右端点在 $\max(l_x,l_y)$ 左边的区间必然不与 $x$ 和 $y$ 中的某一个区间相交，端点在 $\min(r_x,r_y)$ 右边的区间必然不与另一个区间相交）。维护前缀最小和后缀最小即可。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,inf=(int)1e18+5;
int a[N],l[N],r[N],minl[N<<1],minr[N<<1];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<=n*2+1;i++)minl[i]=minr[i]=inf;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        minl[r[i]]=min(minl[r[i]],a[i]);
        minr[l[i]]=min(minr[l[i]],a[i]);
    }
    for(int i=1;i<=n*2;i++)minl[i]=min(minl[i-1],minl[i]);
    for(int i=n*2;i>=1;i--)minr[i]=min(minr[i+1],minr[i]);
    int q;
    cin>>q;
    for(int x,y;q>=1;q--)
    {
        cin>>x>>y;
        int ans=a[x]+a[y];
        if(r[x]>=l[y]&&r[y]>=l[x])
        {
            int l1=min(l[x],l[y]),r1=max(r[x],r[y]);
            int tmp=min(minl[l1-1],minr[r1+1]);
            if(l[x]<=l[y]&&r[x]<=r[y]||l[y]<=l[x]&&r[y]<=r[x])
            {
                int l2=max(l[x],l[y]),r2=min(r[x],r[y]);
                tmp=min(tmp,minr[r2+1]+minl[l2-1]);
            }
            if(tmp==inf)ans=-1;
            else ans+=tmp;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

【题解】[ARC193A] Complement Interval Graph

文章操作

题意

思路

代码

相关推荐

评论

【题解】[ARC193A] Complement Interval Graph