首页 > 其他分享 >CF1961E Turtle and Intersected Segments 题解

CF1961E Turtle and Intersected Segments 题解

时间:2024-06-01 21:11:05浏览次数:28  
标签:Turtle ch int 题解 Segments edge id se define

题目链接

点击打开链接

题目解法

不是,我这咋不会做/fn

边数很多的最小生成树有一个方法是 \(boruvka\),但这个处理完全图的比较方便
另一个方法是用到一个 \(trick\):连出的图中的环,可以删去最长边

扫描线是容易想到的,主要是如何把连的边数缩减到合理的范围内
考虑扫描线到当前时刻时,我们已经维护出了这个时刻存在的区间
给出结论:加点 \(x\) 时,我们只需要 \(x\) 连到当前时刻存在的比 \(v_x\) 恰好大的和恰好小的点
证明手画一画就可以了

最后连出的边数是 \(O(n)\) 的,直接求 \(mst\) 即可
时间复杂度 \(O(n\log n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=500010;
int l[N],r[N],v[N],disc[N<<1];
vector<int> ins[N<<1],del[N<<1];
#define fi first
#define se second
set<pii> se;
typedef tuple<int,int,int> tup;
tup edge[N<<1];
int fa[N];
int gfa(int x){ return x==fa[x]?x:fa[x]=gfa(fa[x]);}
void work(){
    int n;read(n);
    F(i,1,n) read(l[i]),read(r[i]),read(v[i]);
    int cnt=0;
    F(i,1,n) disc[++cnt]=l[i],disc[++cnt]=r[i];
    sort(disc+1,disc+cnt+1);
    cnt=unique(disc+1,disc+cnt+1)-disc-1;
    F(i,1,n){
        l[i]=lower_bound(disc+1,disc+cnt+1,l[i])-disc;
        r[i]=lower_bound(disc+1,disc+cnt+1,r[i])-disc;
        ins[l[i]].pb(i),del[r[i]+1].pb(i);
    }
    int tote=0;
    F(i,1,cnt+1){
        for(int id:del[i]) se.erase({v[id],id});
        for(int id:ins[i]){
            if(!se.empty()){
                auto itr=se.lower_bound({v[id],id});
                if(itr!=se.end()) edge[++tote]={(itr->fi)-v[id],id,itr->se};
                if(itr!=se.begin()){
                    auto itl=prev(itr);
                    edge[++tote]={v[id]-(itl->fi),id,itl->se};
                }
            }
            se.insert({v[id],id});
        }
    }
    sort(edge+1,edge+tote+1);
    F(i,1,n) fa[i]=i;
    LL ans=0;int con=0;
    F(i,1,tote){
        auto [z,x,y]=edge[i];x=gfa(x),y=gfa(y);
        if(x!=y) ans+=z,fa[x]=y,con++;
    }
    if(con==n-1) printf("%lld\n",ans);else puts("-1");
    F(i,1,cnt+1) ins[i].clear(),del[i].clear();
}
int main(){
    int T;read(T);
    while(T--) work();   
    return 0;
}

标签:Turtle,ch,int,题解,Segments,edge,id,se,define
From: https://www.cnblogs.com/Farmer-djx/p/18226413

相关文章

  • 第二十一届宁波大学程序设计竞赛(同步赛) A,B,D,F,H题解
    链接:第二十一届宁波大学程序设计竞赛(同步赛)_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ(nowcoder.com)A:直接输出不多解释B:B-LoveYouGuys_第二十一届宁波大学程序设计竞赛(同步赛)(nowcoder.com)#include<bits/stdc++.h>usingnamespacestd;intx,y......
  • atcoder350,351,352,353,354,355期部分题解
    声明:有些题感觉已经说到很明白了,就先不写代码了,有空会补上目录350D: newfriend350E:toward0351D:GridandMagnet352D:permutation subsequence353C:sigmaproblem353D:anothersigmaproblem354C:atcodermagics355C:bingo2355D:intersectingintervals......
  • 【问题解决】MySQL恢复数据库报错Unknown command '\''.
    问题使用以下命令备份恢复数据库,恢复失败提示ERRORatline39595:Unknowncommand'\''.#备份数据库mysqldump-uusername-p--no-create-db-Rdatabasename>dump.sql#恢复数据库mysql-uusername-pdatabasename2<dump.sql问题原因及解法原因:中文字符的问题......
  • P6156 简单题 题解
    P6156简单题题解题目大意题目传送门给定\(n,k\),求\(\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\gcd(i,j)\mu^2(\gcd(i,j))\)。\(1\leqn\leq5\times10^6\)题目分析先推导一波式子:\[\begin{aligned}ans&=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\gcd(i,j)\mu^2(\gcd(i,j))\\&=......
  • 磁盘管理后续——盘符漂移问题解决
    之前格式化磁盘安装了文件系统,且对磁盘做了相应的挂载,但是服务器重启后挂载信息可能有问题,或者出现盘符漂移、盘符变化、盘符错乱等故障,具体是dev/sda,sdb,sdc等等在某些情况下会混乱掉比如sda变成了sdb或者sdc变成了sdb等等,这样无形中会导致磁盘设备管理的混乱,最常见......
  • 2024ICPC武汉邀请赛E. Boomerang 题解
    E-Boomerang(动态维护树的直径+二分)分析代码实现#include<bits/stdc++.h>#ifdefLOCAL#include"algo/debug.h"#else#definedebug(...)42#endif#defineintlonglongusingEdge=int;structHLD{ intn,times=0; std::vector<int>siz,top,......
  • ARC119F 题解
    blog。被自动机做法恶心到了,现在也来恶心一下大家。\(\color{red}\textbf{以下内容强烈建议自己推一遍,几乎一半是重复的,推完会很爽,并且理解会很深。}\)\(\color{red}\textbf{以下内容不建议用}\LaTeX\textbf{书写,因为写起来像在吃大便。}\)暴力\(dp_{i,a,b}\)表示当前在\(......
  • 【题解】UOJ#284 快乐游戏鸡
    题目大意给出一棵有\(n\)个节点的树,编号为\(i\)的点权为\(w_i\),在树上通过一条边需要花费时间\(1\),如果能通过一个点权为\(w_i\)的点当且仅当此时的死亡次数大于等于\(w_i\),否则会立即回到起点并且死亡次数加一。给出\(q\)组询问,每组询问给出起点\(s\)和终点\(t\),......
  • CF1981D题解
    CF1981D题解前言标签:筛法,欧拉回路。赛后过的,构造一眼秒,欧拉图写错了,多少有点抽象。题意构造一个长度为\(n\)的序列\(a\),需要满足:\(\forall1\lei\len\),\(1\lea_i\le3\times10^5\)。\(\forall1\lei<j<n\),\(a_i\timesa_{i+1}\nea_j\timesa_{j+1}\)。......
  • 题解合集
    CF1270FAwesomeSubstringsCF1860CGameonPermutationP10161[DTCPC2024]小方的疑惑10P10236[yLCPC2024]D.排卡P10368「LAOI-4」ColorsP10369「LAOI-4」MexTower(Easyver.)P10370「LAOI-4」MexTower(Hardver.)P2398GCDSUMP2568GCDP8445射命丸文的取材......