这跟暴力又有什么区别呢？

题解 #

我们先将所有线段的以pair<起点或终点的坐标,线段的序号>的形式存到数组里，然后再将数组排序，然后遍历数组。同时我们还需要维护一个“开放的线段”的右端点的集合。当我们添加一条新的线段时，遍历集合，然后找到比新线段早结束的线段。

这看起来是不是很像暴力？如果要是处理完所有线段是肯定超时的，但是如果交点的个数已经大于 $n-1$ 了，那么答案肯定是 no，所以直接结束就行。

最后还要检查一下图的连通性，用 dfs 或并查集都行。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
 
const int N=5e5+5;
vector<int> G[N];
bool vis[N];
void dfs(int v){
    vis[v]=true;
    for(auto it:G[v]){
        if(!vis[it])
            dfs(it);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int n;
    cin>>n;
    vector<pii> a(n),evs;
    forn(i,n){
        cin>>a[i].F>>a[i].S;
        evs.eb(a[i].F,i);
        evs.eb(a[i].S,i);
    }
    sort(evs.begin(),evs.end());
    int cnt=0;
    set<pii> cur;
    for(auto it:evs){
        if(cnt>=n) break;
        if(cur.count(it)) cur.erase(it);
        else{
            int i=it.S;
            int r=a[i].S;
            for(auto j:cur){
                if(j.F>r) break;
                G[i].pb(j.S);
                G[j.S].pb(i);
                cnt++;
                if(cnt>=n) break;
            }
            cur.insert({r,i});
        }
    }
    dfs(0);
    int tot=count(vis,vis+n,true);
    cout<<(cnt==n-1&&tot==n?"YES":"NO");
    return 0;
}

Codeforces 1248D - Segment Tree 题解

题解 #

Code #