#include<iostream>
#include<utility>
using namespace std;

struct heap
{
    int l,r;
    
    int m,line,count;
    bool lcover,rcover;
};

struct cor
{
    int x,ysma,ybig;
    bool side;
};

void build(int pos,int l,int r);
void insert(int pos,int l,int r);
void remove(int pos,int l,int r);
int updatem(int pos);
pair<int,pair<bool,bool> > updateline(int pos);
void quicksort(int l,int r);
int juedui(int a,int b);

cor cor_x[10020];
heap y[100000];

int main()
{
    int n,min=10001,max=-10001,sum=0,j,i,temp1,temp2,templine;
	cin>>n;
    for(i=0;i<n;i++)
    {
        cin>> cor_x[2*i].x>> cor_x[2*i].ysma;
        cin>> cor_x[2*i+1].x >> cor_x[2*i].ybig;
        cor_x[2*i+1].ysma=cor_x[2*i].ysma;
        cor_x[2*i+1].ybig=cor_x[2*i].ybig;
        cor_x[2*i].side=true;
        cor_x[2*i+1].side=false;
        if(cor_x[2*i].ysma<min)
            min=cor_x[2*i].ysma;
        if(cor_x[2*i].ybig>max)
            max=cor_x[2*i].ybig;
    }
    quicksort(0,2*n-1);
    
    build(1,min,max);
    
    j=0;
    cor_x[2*n].x=-10001;
    //cout<<endl;
    while(j<2*n)
    {
        if(cor_x[j].side)
            insert(1,cor_x[j].ysma,cor_x[j].ybig);
        else
            remove(1,cor_x[j].ysma,cor_x[j].ybig);
        if(cor_x[j].x!=cor_x[j+1].x)
        {
            temp1=y[1].m;
            updatem(1);
            temp2=y[1].m;
            updateline(1);
            templine=y[1].line;
            sum+=templine*2*(juedui(cor_x[j+1].x,cor_x[j].x));
            sum+=juedui(temp1,temp2);
        }
        j++;
    }
    
    cout<<sum<<endl;
    
    return 0;
}
void build(int pos,int l,int r)
{
    y[pos].l=l;
    y[pos].r=r;
    y[pos].m=0;
    y[pos].line=0;
    y[pos].count=0;
    y[pos].lcover=false;
    y[pos].rcover=false;
    if(r-l>1)
    {
        build(2*pos,l,(l+r)/2);
        build(2*pos+1,(l+r)/2,r);
    }
}
void insert(int pos,int l,int r)
{
    if(l<=y[pos].l&&r>=y[pos].r)
        y[pos].count++;
    else if(l>=y[pos].r || r<=y[pos].l)
        return ;
    else if(y[pos].r-y[pos].l!=1)
    {
        insert(2*pos,l,r);
        insert(2*pos+1,l,r);
    }
}

void remove(int pos,int l,int r)
{
    if(l<=y[pos].l&&r>=y[pos].r)
        y[pos].count--;
    else if(l>=y[pos].r||r<=y[pos].l)
        return ;
    else if(y[pos].r-y[pos].l!=1)
    {
        remove(2*pos,l,r);
        remove(2*pos+1,l,r);
    }
}

int updatem(int pos)
{
    if(y[pos].count!=0)
        y[pos].m=y[pos].r-y[pos].l;
    else if(y[pos].r-y[pos].l==1)
        y[pos].m=0;
    else
        y[pos].m=updatem(2*pos)+updatem(2*pos+1);
    return y[pos].m;
}

pair<int,pair<bool,bool> > updateline(int pos)
{
    pair<bool,bool>a;
    pair<int , pair<bool,bool> >b;
    if(y[pos].count!=0)
    {
        y[pos].lcover=y[pos].rcover=true;
        y[pos].line=1;
        a.first=a.second=true;
        b.first=y[pos].line;
        b.second=a;
    }
    else if(y[pos].r-y[pos].l==1)
    {
        y[pos].lcover=y[pos].rcover=false;
        y[pos].line=0;
        a.first=a.second=false;
        b.first=0;
        b.second=a;
    }
    else
    {
        pair<int , pair<bool,bool> >c;
        b=updateline(2*pos);
        c=updateline(2*pos+1);
        y[pos].line=b.first=b.first+c.first-b.second.second * c.second.first;
        y[pos].lcover=b.second.first;
        y[pos].rcover=b.second.second=c.second.second;
    }
    
    return b;
}

void quicksort(int l,int r)
{
    if(l<r)
    {
        int i=l,j;
        cor temp;
        for(j=l;j<r;j++)
        {
            if(cor_x[j].x<cor_x[r].x)
            {
                temp=cor_x[j];
                cor_x[j]=cor_x[i];
                cor_x[i]=temp;
                i++;
            }
        }
        temp=cor_x[r];
        cor_x[r]=cor_x[i];
        cor_x[i]=temp;
        quicksort(l,i-1);
        quicksort(i+1,r);
    }
}

int juedui(int a,int b)
{
    if(a>b)
        return a-b;
    else
        return b-a;
}

• Re:失败啊，照着陈牛的思路写都过不了。。。众神啊，救救我吧。。。 (36) lizeliang 2009-07-15 10:21:48
  • Re:失败啊，照着陈牛的思路写都过不了。。。众神啊，救救我吧。。。 (14) mzhq 2012-04-02 19:59:12