【题解】[ARC193A] Complement Interval Graph

OneLeft · 2025-02-24 07:35:31 · 题解

题意

给你 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) 右边的区间必然不与另一个区间相交）。维护前缀最小和后缀最小即可。

  代码

  #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;
  }