【学习笔记/模板】扫描线 周长并

先开坑，晚上再写。

P1856 [IOI1998] [USACO5.5] 矩形周长Picture

Code

#include<cstdio>
#include<algorithm>

using namespace std;

const int MAXN = 1e5 + 10;
int n, tot_x, tot_y, last_x, last_y;
long long sum;
int val_x[MAXN], val_y[MAXN];
int x[MAXN], y[MAXN]; //离散化用临时数组

struct Line{
    int s; 
    int l, r;
    int sit;
}line_x[MAXN << 1], line_y[MAXN << 1];

inline bool cmp(const Line &a, const Line &b){
    if(a.s == b.s)
        return a.sit > b.sit;
    return a.s < b.s;
}

struct Segment_Tree{
    struct Tree{
        int l, r;
        int len;
        int cnt; //被整体覆盖了几次 
    }tr[MAXN << 2];

    inline int lson(int rt){
        return rt << 1;
    }

    inline int rson(int rt){
        return rt << 1 | 1;
    }

    inline void Pushup(int rt, int *val){
        if(tr[rt].cnt)
            tr[rt].len = val[tr[rt].r + 1] - val[tr[rt].l];
        else
            tr[rt].len = tr[lson(rt)].len + tr[rson(rt)].len;
    }

    void Build(int rt, int l, int r){
        tr[rt].l = l;
        tr[rt].r = r;
        tr[rt].len = 0;
        tr[rt].cnt = 0;

        if(l == r)
            return;

        int mid = (l + r) >> 1;
        Build(lson(rt), l, mid);
        Build(rson(rt), mid + 1, r);
    }

    void Update(int rt, int l, int r, int data, int *val){
        if(tr[rt].l >= l && tr[rt].r <= r){
            tr[rt].cnt += data;
            Pushup(rt, val);

            return;
        }

        int mid = (tr[rt].l + tr[rt].r) >> 1;
        if(l <= mid) Update(lson(rt), l, r, data, val);
        if(r > mid) Update(rson(rt), l, r, data, val);

        Pushup(rt, val);
    }
}S_x, S_y;

inline int read(){
    int x = 0, f = 1;
    char c = getchar();

    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }

    return x * f;
}

int main(){
    n = read();
    for(register int i = 1; i <= n; i++){
        int x1, y1, x2, y2;
        x1 = read(), y1 = read(), x2 = read(), y2 = read();

        //line_x存横边 
        line_x[(i << 1) - 1].s = y1, line_x[(i << 1)].s = y2;
        line_x[(i << 1) - 1].l = line_x[(i << 1)].l = x1;
        line_x[(i << 1) - 1].r = line_x[(i << 1)].r = x2;
        line_x[(i << 1) - 1].sit = 1; 
        line_x[(i << 1)].sit = -1; 
        x[++tot_x] = x1;
        x[++tot_x] = x2;
        //line_y存竖边
        line_y[(i << 1) - 1].s = x1, line_y[(i << 1)].s = x2;
        line_y[(i << 1) - 1].l = line_y[(i << 1)].l = y1;
        line_y[(i << 1) - 1].r = line_y[(i << 1)].r = y2;
        line_y[(i << 1) - 1].sit = 1; 
        line_y[(i << 1)].sit = -1;
        y[++tot_y] = y1;
        y[++tot_y] = y2;
    }

    n <<= 1; 
    sort(x + 1, x + 1 + tot_x);
    sort(y + 1, y + 1 + tot_y);
    int cnt_x = unique(x + 1, x + 1 + tot_x) - x - 1;
    int cnt_y = unique(y + 1, y + 1 + tot_y) - y - 1;
    for(register int i = 1; i <= n; i++){
        int pos_x1 = lower_bound(x + 1, x + 1 + cnt_x, line_x[i].l) - x;
        int pos_x2 = lower_bound(x + 1, x + 1 + cnt_x, line_x[i].r) - x;
        int pos_y1 = lower_bound(y + 1, y + 1 + cnt_y, line_y[i].l) - y;
        int pos_y2 = lower_bound(y + 1, y + 1 + cnt_y, line_y[i].r) - y;

        val_x[pos_x1] = line_x[i].l;
        val_x[pos_x2] = line_x[i].r;
        line_x[i].l = pos_x1;
        line_x[i].r = pos_x2;

        val_y[pos_y1] = line_y[i].l;
        val_y[pos_y2] = line_y[i].r;
        line_y[i].l = pos_y1;
        line_y[i].r = pos_y2;
    }

    sort(line_x + 1, line_x + 1 + n, cmp);
    sort(line_y + 1, line_y + 1 + n, cmp);
    S_x.Build(1, 1, n);
    S_y.Build(1, 1, n);

    for(register int i = 1; i <= n; i++){
        S_x.Update(1, line_x[i].l, line_x[i].r - 1, line_x[i].sit, val_x);
        S_y.Update(1, line_y[i].l, line_y[i].r - 1, line_y[i].sit, val_y);
        sum += abs(S_x.tr[1].len - last_x) + abs(S_y.tr[1].len - last_y);
        last_x = S_x.tr[1].len;
        last_y = S_y.tr[1].len;
    }

    printf("%lld\n", sum);

    return 0;
}