扫描线入门题

本题前置知识
1. 离散化
2. 线段树

注意点:
1.这题线段树的根节点表示的是一个(l,l+1)的区间,划分[L,R] – [L,mid] 和 [mid,R]
2.线段树开4倍空间

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e4 + 10;
struct node1{
    int sum;
    int cnt;
};
struct node2{
    int x1,x2,y;
    bool j1;
};
node2 arr[N << 1];
node1 tr[N << 2];
int pos[N << 1];
int lazy[N << 2];
bool cmp(node2 a,node2 b)
{
    return a.y < b.y;
}
void build(int l,int r,int u)
{
    if((l + 1) == r){
        tr[u].sum = pos[r] - pos[l];
        return ;
    }
    if((l + 1) >= r)return ;
    int mid = (l + r) >> 1;
    build(l,mid,u << 1);
    build(mid,r,u << 1 | 1);
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int l,int r,int u)
{
    int mid = (l + r) >> 1;
    if(lazy[u])
    {
        tr[u << 1].cnt += lazy[u];
        tr[u << 1 | 1].cnt += lazy[u];
        lazy[u << 1] += lazy[u];
        lazy[u << 1 | 1] += lazy[u];
        lazy[u] = 0;
    }
}
void ud(int l,int r,int a,int b,int d,int u)
{
    if(l <= a && r >= b){
        tr[u].cnt += d;
        lazy[u] += d;
        return ;
    }
    if((a + 1) >= b)return ;
    pushdown(a,b,u);
    int mid = (a + b) >> 1;
    if(l <= mid)ud(l,r,a,mid,d,u << 1);
    if(r >= mid)ud(l,r,mid,b,d,u << 1 | 1);
}
int query(int l,int r,int a,int b,int u)
{
    if(l <= a && b <= r)
    {
        if(tr[u].cnt > 0)return tr[u].sum;
    }
    if((a + 1) >= b)return 0;
    pushdown(a,b,u);
    int mid = (a + b) >> 1;
    int ans = 0;
    if(l <= mid)ans += query(l,r,a,mid,u << 1);
    if(r >= mid)ans += query(l,r,mid,b,u << 1 | 1);
    return ans;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        arr[i] = {x1,x2,y1,0};
        arr[i + n] = {x1,x2,y2,1};
        pos[i] = x1;
        pos[i + n] = x2;
    }
    sort(pos + 1,pos + 2 * n + 1);
    sort(arr + 1,arr + 2 * n + 1,cmp);
    int tot = 1;
    for(int i = 2;i <= 2 * n;i ++)
    {
        if(pos[i] != pos[tot])pos[++ tot] = pos[i];
    }
    build(1,tot,1);
    int ans = 0;
    for(int i = 1;i <= 2 * n;i ++)
    {
        int t1 = 1,t2 = 1;
        int l = 1,r = tot;
        int x1 = arr[i].x1,x2 = arr[i].x2;
        bool t = arr[i].j1;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(pos[mid] >= x1)r = mid;
            else l = mid + 1;
        }
        t1 = l;
        l = 1,r = tot;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(pos[mid] >= x2)r = mid;
            else l = mid + 1;
        }
        t2 = l;
        ans += query(1,tot,1,tot,1) * (arr[i].y - arr[i - 1].y);
        if(t1 == t2)continue;
        if(t)ud(t1,t2,1,tot,-1,1);
        else ud(t1,t2,1,tot,1,1);
    }
    cout << ans << endl;
}