版权声明：欢迎关注我的博客。本文为博主【炒饭君】原创文章，未经博主同意不得转载 https://blog.csdn.net/a1061747415/article/details/25471349

Problem A : Counting Squares

pid=1264" rel="nofollow">From:HDU, 1264

题目大意：

 给定你一些矩形左下右上角坐标点。或者左上右下坐标点。求这些矩形的面积并。

解题思路：

利用线段树扫描线的知识。此题不须要离散化。

#include <iostream>

#include <cmath>

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

struct node{

    int x,y1,y2,c;

    node(int x0=0,int y10=0,int y20=0,int c0=0){

        x=x0;y1=y10;y2=y20;c=c0;

    }

    friend bool operator < (node a,node b){

        if(a.x!=b.x) return a.x<b.x;

        else if(a.y1!=b.y1) return a.y1<b.y1;

        else if(a.y2!=b.y2) return a.y2<b.y2;

        else return a.c>b.c;

    }

};

const int maxh=110;

struct tree{

    int l,r,c,lz;

}a[maxh*4];

vector <node> v;

bool input(){

    int a,b,c,d;

    v.clear();

    while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){

        if(a==-1 && b==-1 && c==-1 && d==-1) return true;

        if(a==-2 && b==-2 && c==-2 && d==-2) return false;

        v.push_back(node( min(a,c), min(b,d) , max(b,d) ,1));

        v.push_back(node( max(a,c), min(b,d) , max(b,d) ,-1));

    }

}

void build(int l,int r,int k){

    a[k].l=l;

    a[k].r=r;

    a[k].c=0;

    a[k].lz=0;

    if(l+1<r){

        int mid=(l+r)/2;

        build(l,mid,2*k);

        build(mid,r,2*k+1);

    }

}

void pushdown(int k){

    if(a[k].lz!=0 && a[k].l+1<a[k].r ){

        a[2*k].lz+=a[k].lz;

        a[2*k+1].lz+=a[k].lz;

        a[2*k].c+=a[k].lz;

        a[2*k+1].c+=a[k].lz;

        a[k].lz=0;

    }

}

void insert(int l,int r,int k,int c){

    if(l<=a[k].l && a[k].r<=r){

        a[k].lz+=c;

        a[k].c+=c;

    }else{

        pushdown(k);

        int mid=(a[k].l+a[k].r)/2;

        if(r<=mid) insert(l,r,2*k,c);

        else if(l>=mid) insert(l,r,2*k+1,c);

        else{

            insert(l,mid,2*k,c);

            insert(mid,r,2*k+1,c);

        }

    }

}

int query(int l,int r,int k){

    pushdown(k);

    if(l<=a[k].l  && a[k].r<=r){

        if(a[k].c>0) return r-l;

        else{

            if(a[k].l+1==a[k].r) return 0;

            else {

                int mid=(a[k].l+a[k].r)/2;

                return query(l,mid,2*k) + query(mid,r,2*k+1) ;

            }

        }

    }else{

        int mid=(a[k].l+a[k].r)/2;

        if(r<=mid) return query(l,r,2*k);

        else if(l>=mid) return query(l,r,2*k+1);

        else{

            return query(l,mid,2*k) + query(mid,r,2*k+1) ;

        }

    }

}

void solve(){

    build(0,maxh,1);

    sort(v.begin(),v.end());

    insert(v[0].y1,v[0].y2,1,v[0].c);

    int ans=0;

    for(int i=1;i<v.size();i++){

        //cout<<v[i].x-v[i-1].x<<" "<<query(0,maxh,1)<<endl;

        ans+=(v[i].x-v[i-1].x)*query(0,maxh,1);

        insert(v[i].y1,v[i].y2,1,v[i].c);

    }

    cout<<ans<<endl;

}

int main(){

    while(input()){

        solve();

    }

    solve();

    return 0;

}