HDu 3265 Posters(走査線)


題意:いくつかの筋空の矩形を与えて、彼らの面積の和を要求します.1つの矩形を4つの矩形に分解すれば、直接前のものをカバーすることができます.
いくつか注意すべき点があり、答えはintを超えます.リーフノードに直接更新するとタイムアウトします.x 1<=x 3のため、1つのポイントのみが更新されます.
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=200005;
int y[N*2],d;
struct Line
{
    int x,y1,y2,co;
    void fun(int a,int b,int c,int d){x=a;y1=b;y2=c;co=d;}
}line[N*2];
struct node
{
    int left,right,co;
    int lf,rf,len;
    int mid(){return left+(right-left)/2;}
};
struct Segtree
{
    node tree[N*8];
    void build(int left,int right,int r)
    {
        tree[r].left=left;  tree[r].right=right;
        tree[r].lf=y[left]; tree[r].rf=y[right];
        tree[r].co=tree[r].len=0;
        if(left+1<right)
        {
            int mid=tree[r].mid();
            build(left,mid,r*2);
            build(mid,right,r*2+1);
        }
    }
    void updata(Line e,int r)
    {
        if(e.y1<=tree[r].lf&&tree[r].rf<=e.y2)
        {
            tree[r].co+=e.co;
            calen(r);
        }
        else
        {
            if(tree[r].left+1==tree[r].right) return;
            if(e.y1<tree[r*2].rf) updata(e,r*2);
            if(e.y2>tree[r*2+1].lf) updata(e,r*2+1);
            calen(r);
        }
    }
    void calen(int r)
    {
        if(tree[r].co>0)
        {
            tree[r].len=tree[r].rf-tree[r].lf;
        }
        else
        {
            if(tree[r].left+1==tree[r].right){tree[r].len=0;return;} //       。
            else tree[r].len=tree[r*2].len+tree[r*2+1].len;
        }
    }
}seg;
void add_line(int,int,int,int);
int deal(int);
bool cmp(const Line &e1,const Line &e2)
{
    return e1.x<e2.x;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;

        d=0;
        for(int i=0;i<n;i++)
        {
            int x1,y1,x2,y2,x3,y3,x4,y4;
            scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
            add_line(x1,y1,x3,y2);  add_line(x3,y1,x4,y3);
            add_line(x3,y4,x4,y2);  add_line(x4,y1,x2,y2);
        }
        int cnt=deal(d);

        long long ans=0;
        seg.build(0,cnt-1,1);
        seg.updata(line[0],1);
        for(int i=1;i<d;i++)
        {
            ans+=(1LL*seg.tree[1].len*(line[i].x-line[i-1].x));
            seg.updata(line[i],1);
        }
        printf("%I64d
",ans); } return 0; } void add_line(int x1,int y1,int x2,int y2) { line[d].fun(x1,y1,y2,1); y[d++]=y1; line[d].fun(x2,y1,y2,-1); y[d++]=y2; } int deal(int n) { sort(y,y+n); sort(line,line+n,cmp); int cnt=1; for(int i=1;i<n;i++) { if(y[i]!=y[i-1]) y[cnt++]=y[i]; } return cnt; }