[CF1285E] Delete a Segment

题目链接

Solution

这道题似乎有好几种做法来着……不过最直观的是直接上线段树啦～

区间加、求总体的段数……诶，等等，这不是扫描线求矩形周长并的那棵线段树吗！就是那棵没有 pushdown 的神奇线段树啊！（顺便放个链接：关于扫描线算法中线段树标记的理解）

注意一下离散化可能会使原来没有挨着的坐标挨着，所以离散化之后乘个 $2$ 就好了。

然后就没什么好说的了……

Code

#include<algorithm>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

const int N = 400005;

int T, n, t[N], maxx;
struct segment{
    int l, r;
    int dl, dr; // after discretization
}a[N];

inline void disc(){
    sort(t+1, t+t[0]+1);
    t[0] = unique(t+1, t+t[0]+1) - (t+1);
    for(int i = 1; i <= n; i++){
        a[i].dl = lower_bound(t+1, t+t[0]+1, a[i].l) - t;
        a[i].dr = lower_bound(t+1, t+t[0]+1, a[i].r) - t;
        a[i].dl <<= 1, a[i].dr <<= 1;
        maxx = max(maxx, max(a[i].dl, a[i].dr));
    }
}

struct segTree{
    int l, r, cnt, tim;
    bool lcon, rcon;
}tr[N<<3];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
#define len(id) (tr[id].r - tr[id].l + 1)
inline void pushup(int id){
    if(tr[id].cnt){
        tr[id].tim = 1;
        tr[id].lcon = tr[id].rcon = true;
    }
    else if(tr[id].l == tr[id].r){
        tr[id].tim = 0;
        tr[id].lcon = tr[id].rcon = false;
    }
    else{
        tr[id].tim = tr[lid].tim + tr[rid].tim - (tr[lid].rcon && tr[rid].lcon);
        tr[id].lcon = tr[lid].lcon, tr[id].rcon = tr[rid].rcon;
    }
}
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    tr[id].cnt = tr[id].tim = tr[id].lcon = tr[id].rcon = 0;
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void add(int id, int l, int r, int val){
    if(tr[id].l == l && tr[id].r == r){
        tr[id].cnt += val;
        pushup(id);
        return;
    }
    if(r <= mid)    add(lid, l, r, val);
    else if(l > mid)    add(rid, l, r, val);
    else    add(lid, l, mid, val), add(rid, mid+1, r, val);
    pushup(id);
}

int main(){
    read(T);
    while(T--){
        read(n);
        maxx = t[0] = 0;
        for(int i = 1; i <= n; i++){
            read(a[i].l, a[i].r);
            t[++t[0]] = a[i].l, t[++t[0]] = a[i].r;
        }
        disc();
        build(1, 1, maxx);
        for(int i = 1; i <= n; i++)
            add(1, a[i].dl, a[i].dr, 1);
        int ans = 0;
        for(int i = 1; i <= n; i++){
            add(1, a[i].dl, a[i].dr, -1);
            ans = max(ans, tr[1].tim);
            add(1, a[i].dl, a[i].dr, 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}