记录编号	583737	评测结果	AAAAA
题目名称	[IOI 1998] 矩形周长	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-10-21 10:02:28	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
//线段树+扫描线 
const int N = 1e4+10;
int n;
struct made{
    int y,x1,x2,z;
    made(){}
    made(int y,int x1,int x2,int z):y(y),x1(x1),x2(x2),z(z){}
    bool operator < (const made &p)const{
        return (y == p.y ?z > p.z:y < p.y);//!!先加后减 
    }
}line[N];
int h[N];//离散化 
struct segtree{
    int l,r;
    int len,la,num;
    bool lc,rc;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define len(x) t[x].len
    #define la(x) t[x].la
    #define num(x) t[x].num
    #define lc(x) t[x].lc
    #define rc(x) t[x].rc
}t[N<<2];
void build(int x,int l,int r){
    l(x) = l,r(x) = r;
    if(l == r)return;
    int mid = l + r >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
void pushup(int x){
    if(la(x)){
        len(x) = h[r(x)+1] - h[l(x)];
        lc(x) = rc(x) = num(x) = 1;
    }
    else{
        len(x) = len(x<<1) + len(x<<1|1);
        num(x) = num(x<<1) + num(x<<1|1);
        if(rc(x<<1) && lc(x<<1|1))num(x)--;
        lc(x) = lc(x<<1),rc(x) = rc(x<<1|1);
    }
}
void add(int x,int l,int r,int z){
    if(l <= l(x) && r(x) <= r){
        la(x) += z;
        pushup(x);
        return; 
    }
    int mid = l(x) + r(x) >> 1;
    if(l <= mid)add(x<<1,l,r,z);
    if(r > mid)add(x<<1|1,l,r,z);
    pushup(x);
}
int main(){
    freopen("picture.in","r",stdin);
    freopen("picture.out","w",stdout);
    scanf("%d",&n);
    int cnt = 0;
    for(int i = 1;i <= n;i++){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        cnt++;
        h[cnt] = x1,line[cnt] = made(y1,x1,x2,1);
        cnt++;
        h[cnt] = x2,line[cnt] = made(y2,x1,x2,-1);
    }
    sort(h+1,h+1+cnt);
    sort(line+1,line+1+cnt);
    int m = unique(h+1,h+1+cnt) - (h+1);
    build(1,1,m-1);
    long long ans = 0,pre = 0;
    for(int i = 1;i <= cnt;i++){
        int l = lower_bound(h+1,h+1+m,line[i].x1) - h;
        int r = lower_bound(h+1,h+1+m,line[i].x2) - h;
        add(1,l,r-1,line[i].z);
        ans += abs(t[1].len - pre),pre = t[1].len;
        if(i < cnt)ans += t[1].num * 2 * (line[i+1].y - line[i].y);
    }
    printf("%lld\n",ans);
    
    return 0;
    
}