线段树 + 离散化

思路+重点

1. 线段树法求面积，以y轴为线段构造线段树，横向扫描
2. 坐标范围过大无法开数组 => 离散化
3. 结果需要用long long

对于离散化的细节还没有很清楚,记录一下

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long LL;
const LL N = 1e3+10;
//尝试离散化

unordered_map<int,int> val;
int raw[2*N];

struct Segment
{
    int x,y1,y2,k;
    bool operator< (const Segment &t) const
    {
        return x<t.x;
    }
}Se[N*2];

struct Node{
    int l,r,len,cnt;
}tr[N*8];

void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    if(l == r) return;
    int mid = (tr[u].l + tr[u].r) >> 1;
    build(u<<1, l, mid);
    build(u<<1|1, mid+1, r);
}

void pushup(int u)
{
    if(tr[u].cnt > 0) tr[u].len = raw[tr[u].r+1] - raw[tr[u].l] ;
    else if(tr[u].l == tr[u].r) tr[u].len = 0;
    else{
        tr[u].len = tr[u<<1].len + tr[u<<1|1].len;
    }
}


void modify(int u, int l, int r, int k)
{
    if(l <= tr[u].l && tr[u].r <= r) 
    {
        tr[u].cnt += k;
        pushup(u);
    }else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if( l <= mid) modify(u<<1, l, r, k);
        if( r >= mid+1) modify(u<<1|1, l ,r, k);
        pushup(u);
    }
}

int n;
int main()
{
    scanf("%d",&n);
    int x1,y1,x2,y2;
    int m=0;
    for(int i = 0; i < n; i++ )
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        raw[m] = y1;
        Se[m++] = {x1,y1,y2,1};
        raw[m] = y2;
        Se[m++] = {x2,y1,y2,-1};

    }
    sort(raw, raw+2*n);
    // m = unique(raw, raw+2*n)-raw;

    // y的坐标映射到0-m之间
    for(int i = 0; i < m; i++) val[raw[i]] = i;

    sort(Se,Se + 2*n);
    build(1, 0, m);

    LL res = 0;
    for(int i = 0; i < m; i++)
    {
        if(i > 0)  res += (LL)tr[1].len * (LL)(Se[i].x - Se[i-1].x);

        modify(1, val[Se[i].y1], val[Se[i].y2]-1, Se[i].k);
        // cout<<tr[1].len<<" "<<(Se[i].x - Se[i-1].x)<<" "<<res<<endl;
    }

    printf("%lld\n",res);
    return 0;
}