CF1691E 解题报告

elbissoPtImaerD · 2024-05-23 11:42:27 · 题解

不需要 \log 数据结构的做法。

考虑加入这个区间 [l,r] 后会将哪些区间合并。维护前面的异色线段然后暴力扫一遍是平方的。

考虑优化，由于此区间对一个连通块至多只需连一条边，所以使用并查集维护连通块，若将所有区间按右端点升序排序，则一个连通块的代表元只需要取右端点最右的那个即可。

而且排序后的序列有单调性，能连边的一定是一段后缀，所以对每个颜色维护一个单调栈状物即可。

这样均摊下来只有并查集的复杂度，是 O(n\alpha(n)) 的。

il void Solve()
{
  int n;cin>>n;
  ve<tuple<int,int,int>>e(n);
  for(auto&[o,l,r]:e) cin>>o>>l>>r;
  DSU S(n);
  int ans=n;
  ve<int>q[2];
  sort(all(e),[&](auto x,auto y){return get<2>(x)<get<2>(y);});
  for(int _=0;_<n;++_) {
    auto[o,l,r]=e[_];
    for(int lst=-1;;) {
      if(!q[o].size()) {
        if(~lst) q[o].pb(lst);
        break;
      }
      int i=q[o].back();
      if(l<=get<2>(e[i])) {
        ans-=S.Merge(i,_);
        if(!~lst) lst=i;
        q[o].pop_back();
      }
      else {
        if(~lst) q[o].pb(lst);
        break;
      }
    }
    q[o^1].pb(_);
  }
  cout<<ans<<'\n';
  return;
}

\color{green}{\checkmark}