CF1981E Turtle and Intersected Segments 题解

· · 题解

赛时降智了写树套树结果没调完，赛后才发现扫描线 + 只查前驱后继直接用 std::multiset 即可。错失一个场切 \color{Red}*2700，寄。

暴力建图显然不可取，考虑使用限制减少边数。猜测对于某一条线段 i，它只需要向与它相交且左端点不大于它的线段 j 中的（最多）两条线段连边：第一条为 a_j\le a_i 且 a_j 最大的线段，第二条为 a_j>a_i 且 a_j 最小的线段；最后在这个图上跑 MST 即可。证明可以考虑 Kruskal 算法的流程，如果两点已经连通那么边权更大的边就不需要也不可以加入最小生成树，对于三条两两相交的线段简单讨论即可。

现在问题在于如何找出上面的这（最多）两条线段。可以用一种比较麻烦的线段树套平衡树 + 二分进行维护；但是并不需要。参考官方题解做法，离散化后按照位置从左往右进行扫描线：对于每一条线段 [l_i,r_i] 在扫到 l_i 时往一个多重集合里面加入 a_i，在 r_i 时删除 a_i；插入时查找集合中 a_i 的前驱后继，建边即可。最后跑一遍 Kruskal。

时间复杂度 O(n\log n)，略带常数（std::multiset）但时限 5\mathrm{s} ，n=5\times 10^5 轻松通过，甚至跑不到 2\mathrm{s}。

参考代码（GNU C++17）：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s;
    public:
      dsu(){
        a.resize(200000),s.resize(200000,1);
        iota(a.begin(),a.end(),0);
      }
      dsu(int n){
        a.resize(n),s.resize(n,1);
        iota(a.begin(),a.end(),0);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      inline int size(T x){
        return s[leader(x)];
      }
      inline void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      inline bool same(T x,T y){
        return leader(x)==leader(y);
      }
  };
} // 并查集模板
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n,c=0; long long mst=0; cin>>n;
    vector<tpi> a(n),e;
    vector<int> b;
    for(auto &[l,r,w]:a)
      cin>>l>>r>>w,b.emplace_back(l),b.emplace_back(r);
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    vector<vector<pii> > q1(n<<1),q2(n<<1);
    for(int i=0;i<n;i++){
      auto &[l,r,w]=a[i];
      l=lower_bound(b.begin(),b.end(),l)-b.begin();
      r=lower_bound(b.begin(),b.end(),r)-b.begin();
      // 离散化
      q1[l].emplace_back(w,i);
      q2[r].emplace_back(w,i);
    }
    multiset<pii> s;
    for(int t=0;t<n<<1;t++){ // 进行扫描线
      for(auto i:q1[t]){
        auto p=s.lower_bound(make_pair(i.first,0));
        if(p!=s.end())e.emplace_back(i.second,p->second,p->first-i.first);
        p=s.upper_bound(make_pair(i.first+1,0));
        if(p!=s.begin())e.emplace_back(i.second,prev(p)->second,i.first-prev(p)->first);
        s.emplace(i);
      } // 加入线段并查找前驱后继
      for(auto i:q2[t])
        s.erase(s.find(i)); // 删除线段
    }
    sort(e.begin(),e.end(),[](tpi x,tpi y){
      return get<2>(x)<get<2>(y);
    });
    IAOI_lib::dsu<int> d(n);
    for(auto [u,v,w]:e)
      if(!d.same(u,v))d.merge(u,v),c++,mst+=w;
    // 跑一遍 Kruskal
    cout<<(c==n-1?mst:-1)<<'\n';
  }
  return 0;
}