Sweep Line: Algorithm, Mathematics, Complexity, and Applications

1. Algorithm Overview

The sweep line (or line-sweep) technique “sweeps” a line (usually vertical) across the plane, processing events in sorted order and maintaining an active set of objects (intervals, segments, points) in a data structure (balanced BST, multiset, segment tree…).

Typical steps:

1. Generate events for each object (e.g. for an interval [l,r]: “enter” at x=l, “exit” at x=r).
2. Sort all events by x-coordinate (breaking ties: “enter” before “exit”).
3. Maintain an active set of objects—insert on “enter”, remove on “exit”.
4. At each event you can query the active set to compute answers (e.g. maximum overlap, nearest neighbor, area contribution, etc.).

Time Complexity

• Sorting E events: O(E log E).
• Each insertion/removal/query in active structure: typically O(log E).

Total: O(E log E).

Memory Complexity

Storing events and active structure of size ≤ E: O(E).

---

2. Mathematics of Sweep Line

• Event ordering: ensure correctness by sorting events by x, tie-breaking enters before exits so intervals of zero length are handled.
• Active set invariants: at sweep-line position x, the active set contains exactly those objects intersecting the vertical line x=const.
• Area by integration: when computing union of rectangles, track the total covered length L(x) at each x, then area = ∫ L(x) dx ≈ Σ L(x_i)·(x_{i+1}−x_i).

---

3. Easy Problems

3.1 – Codeforces 610D “Points on a Line”

Given N vertical intervals [l_i, r_i] on the x-axis, find the maximum number of intervals that overlap at any point.

Input:
5
1 4
2 5
3 6
5 7
6 8

Output:
3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N; cin >> N;
    vector<pair<int,int>> events;
    for(int i=0;i<N;i++){
        int l,r; cin>>l>>r;
        events.emplace_back(l, +1);   // enter
        events.emplace_back(r, -1);   // exit
    }
    sort(events.begin(), events.end(),
        [](auto &a, auto &b){
            if(a.first!=b.first) return a.first<b.first;
            return a.second>b.second; // enter before exit
        });
    int cur=0, best=0;
    for(auto &e: events){
        cur += e.second;
        best = max(best, cur);
    }
    cout << best << "\n";
    return 0;
}

3.2 – Codeforces 1117C “Union of Segments Length”

Given N intervals [l_i,r_i], compute the total length covered by their union. Use sweep-line + maintain current coverage count and last x.

Input:
3
1 3
2 5
6 8

Output:
5

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N; cin>>N;
    vector<pair<int,int>> ev;
    for(int i=0;i<N;i++){
        int l,r; cin>>l>>r;
        ev.emplace_back(l, +1);
        ev.emplace_back(r, -1);
    }
    sort(ev.begin(), ev.end());
    int count=0;
    int lastX = ev[0].first;
    long long total=0;
    for(auto &e: ev){
        int x=e.first, delta=e.second;
        if(count>0) total += x - lastX;
        count += delta;
        lastX = x;
    }
    cout << total << "\n";
    return 0;
}

---

4. Intermediate Problems

4.1 – Codeforces 1462F “The Treasure of The Segments”

Given N segments [l_i,r_i] and an integer K, find the maximum possible sum of lengths of K non-overlapping segments chosen from the set. Approach: sweep-line + a multiset of lengths of “active” segments, always keep only top K.

Input:
5 2
1 5
2 6
4 7
8 10
9 11

Output:
8

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;

int main(){
    int N,K; cin>>N>>K;
    vector<pair<int,pair<int,int>>> ev;
    for(int i=0;i<N;i++){
        int l,r; cin>>l>>r;
        ev.push_back({l, {+1, r-l}});
        ev.push_back({r, {-1, r-l}});
    }
    sort(ev.begin(), ev.end());
    multiset<int> active;
    ll sum = 0, best = 0;
    for(auto &e: ev){
        int type = e.second.first, len = e.second.second;
        if(type == +1){
            active.insert(len);
            sum += len;
            if(active.size() > K){
                auto it = prev(active.end());
                sum -= *it;
                active.erase(it);
            }
        } else {
            // removal: erase one instance if present
            auto it = active.find(len);
            if(it != active.end()){
                sum -= len;
                active.erase(it);
            }
        }
        best = max(best, sum);
    }
    cout << best << "\n";
    return 0;
}

4.2 – Codeforces 920E “Connected Components in a Dynamic Graph”

We have N nodes on a line, and M operations adding/removing an edge between consecutive nodes. After each operation, report number of connected components. Sweep over operations in time, maintain a BIT counting active edges; components = N − active_edges.

Input:
5 4
+ 2
+ 4
- 2
+ 3

Output:
4
3
4
3

#include <iiostream>
#include <vector>
#include <string>
using namespace std;

int main(){
    int N, M; cin >> N >> M;
    vector<bool> active(N,false);
    int activeEdges = 0;
    while(M--){
        char op; int x;
        cin >> op >> x;  // edge between x and x+1
        if(op == '+'){
            if(!active[x]){
                active[x]=true;
                activeEdges++;
            }
        } else {
            if(active[x]){
                active[x]=false;
                activeEdges--;
            }
        }
        cout << (N - activeEdges) << "\n";
    }
    return 0;
}

---

5. Hard Problem

5.1 – Codeforces 1199F “Rectangle Area Union”

Given N axis-aligned rectangles, compute the total area of their union. Classic sweep-line:

• Events at x = left (add [y1,y2]), x = right (remove [y1,y2]).
• Maintain a segment tree over y-coordinates storing covered length.
• Sum area += covered_length * (x_{i+1}−x_i).

Input:
3
1 1 4 3
2 2 5 5
3 0 6 2

Output:
14

#include <iiostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct Event {
    int x, y1, y2, type;
    bool operator<(const Event&o) const {
        return x < o.x;
    }
};

struct SegTree {
    int n;
    vector<int> cnt;
    vector<ll> len;
    vector<int> ys;
    SegTree(const vector<int>& ys_): ys(ys_) {
        n = ys.size()-1;
        cnt.assign(4*n, 0);
        len.assign(4*n, 0);
    }
    void update(int idx,int l,int r,int ql,int qr,int v){
        if(ql>r || qr<l) return;
        if(ql<=l && r<=qr){
            cnt[idx]+=v;
        } else {
            int m=(l+r)/2;
            update(idx*2,l,m,ql,qr,v);
            update(idx*2+1,m+1,r,ql,qr,v);
        }
        if(cnt[idx]>0) len[idx]=ys[r+1]-ys[l];
        else if(l==r) len[idx]=0;
        else len[idx]=len[idx*2]+len[idx*2+1];
    }
};

int main(){
    int N; cin>>N;
    vector<Event> ev;
    vector<int> Y;
    for(int i=0;i<N;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        ev.push_back({x1,y1,y2, +1});
        ev.push_back({x2,y1,y2, -1});
        Y.push_back(y1);
        Y.push_back(y2);
    }
    sort(Y.begin(),Y.end());
    Y.erase(unique(Y.begin(),Y.end()),Y.end());
    sort(ev.begin(),ev.end());
    SegTree st(Y);
    ll area=0;
    for(int i=0;i+1<ev.size();i++){
        int y1 = lower_bound(Y.begin(),Y.end(), ev[i].y1) - Y.begin();
        int y2 = lower_bound(Y.begin(),Y.end(), ev[i].y2) - Y.begin() - 1;
        st.update(1,0,st.n-1,y1,y2, ev[i].type);
        ll width = ev[i+1].x - ev[i].x;
        area += st.len[1] * width;
    }
    cout<<area<<"\n";
    return 0;
}