怎么判断两个线段重叠
1.动态开点线段树 code

struct Segtree{
    int ls, rs;
    int sum, tag;
}tr[N << 6];
inline void pushup(int p){ 
    tr[p].sum = tr[tr[p].ls].sum + tr[tr[p].rs].sum;
}
inline void pushdown(int p, int l, int r){
    if(!tr[p].ls) tr[p].ls = ++ num;
    if(!tr[p].rs) tr[p].rs = ++ num;
    auto &root = tr[p], &left = tr[tr[p].ls], &right = tr[tr[p].rs];
    if(root.tag){
        int mid = l + r >> 1;
        left.sum += (mid - l + 1) * root.tag;
        right.sum += (r - mid) * root.tag;
        left.tag += root.tag;
        right.tag += root.tag;
        root.tag = 0;
    }
    return;
}
inline void modify(int &p, int l, int r, int cl, int cr, int w){
    if(!p) p = ++ num;
    if(cl <= l && r <= cr){
        tr[p].sum += (r - l + 1) * w;
        tr[p].tag += w;
        return;
    }
    pushdown(p, l, r);
    int mid = l + r >> 1;
    if(cl <= mid) modify(tr[p].ls, l, mid, cl, cr, w);
    if(mid < cr) modify(tr[p].rs, mid + 1, r, cl, cr, w);
    pushup(p);
}
inline int query(int p, int l, int r, int cl, int cr){
    if(!p) return 0;
    if(cl <= l && r <= cr){
        return tr[p].sum;
    }
    pushdown(p, l, r);
    int mid = l + r >> 1;
    int res = 0;
    if(cl <= mid) res += query(tr[p].ls, l, mid, cl, cr);
    if(mid < cr) res += query(tr[p].rs, mid + 1, r, cl, cr); 
    pushup(p);
    return res;
}

离散化+差分 code

    sort(idx.begin(), idx.end());
    idx.erase(unique(idx.begin(), idx.end()), idx.end());
    vector<vector<tuple<int,int,int>>> C(n << 1|1);
    rep(i, 1, n){
        auto [L, R, col] = a[i];
        int l = lower_bound(idx.begin(), idx.end(), L) - idx.begin();
        int r = lower_bound(idx.begin(), idx.end(), R) - idx.begin();
        C[l].push_back({i, 1, col});
        C[r + 1].push_back({i, -1, col});
    }
    map<int,int> q;
    set<int> id;
    rep(j, 0, siz(idx)){
        for(auto [i, c, col]:C[j]){
            if(c == 1){
                q[col] ++; id.insert(i);
            }else{
                q[col] --;
                if(!q[col]) q.erase(col);
                id.erase(i);
            }
        }
        if(q.size() >= 2){
            for(auto x:id) res[x] = 0;
            id.clear();
        }
    }

基于Codeforces 1741F