HDU 1828 POJ 1177 Picture

矩形周长并

POJ上C++,G++都能过，HDU上C++过了，G++WA ，不知道为什么

#include<cstdio>

#include<cstring>

#include<cmath>

#include<map>

#include<algorithm>

using namespace std;

const int maxn=;

struct Seg

{

    int x;

    int Y1,Y2;//离散化之后的坐标

    int flag;

}s[maxn];

int X1[maxn],X2[maxn],Y1[maxn],Y2[maxn];

map<int ,int>m;

int M[maxn];int k;

int n,tot;

int sum,ans;

struct SegTree

{

    int len;

    int cover;

} segTree[maxn*];

bool cmp(const Seg&a,const Seg&b)

{

    return a.x<b.x;

}

void lsh1()

{

    k=;

    m.clear();

    for(int i=; i<=n; i++)

    {

        if(m[Y1[i]]==) M[k++]=Y1[i],m[Y1[i]]=;

        if(m[Y2[i]]==) M[k++]=Y2[i],m[Y2[i]]=;

    }

    sort(M,M+k);

    m.clear();

    for(int i=; i<k; i++) m[M[i]]=i;

}

void lsh2()

{

    k=;

    m.clear();

    for(int i=; i<=n; i++)

    {

        if(m[X1[i]]==) M[k++]=X1[i],m[X1[i]]=;

        if(m[X2[i]]==) M[k++]=X2[i],m[X2[i]]=;

    }

    sort(M,M+k);

    m.clear();

    for(int i=; i<k; i++) m[M[i]]=i;

}

void build(int l,int r,int rt)

{

    segTree[rt].cover=;

    segTree[rt].len=;

    if(l==r) return;

    int m=(l+r)/;

    build(l,m,*rt);

    build(m+,r,*rt+);

}

void pushUp(int rt,int l,int r)

{

    if(segTree[rt].cover) segTree[rt].len=M[r]-M[l-];

    else segTree[rt].len=segTree[*rt].len+segTree[*rt+].len;

}

void update(int info,int L,int R,int l,int r,int rt)

{

    if(L<=l&&r<=R)

    {

        segTree[rt].cover=segTree[rt].cover+info;

        pushUp(rt,l,r);

        return;

    }

    int m=(l+r)/;

    if(L<=m) update(info,L,R,l,m,*rt);

    if(R>m)  update(info,L,R,m+,r,*rt+);

    pushUp(rt,l,r);

}

int main()

{

    int Case=;

    while(~scanf("%d",&n))

    {

        if(n==)

        {

            printf("0\n");

            continue;

        }

        for(int i=; i<=n; i++)

            scanf("%d%d%d%d",&X1[i],&Y1[i],&X2[i],&Y2[i]);

        lsh1();

        tot=;

        for(int i=; i<=n; i++)

        {

            s[tot].x=X1[i],s[tot].Y1=m[Y1[i]],s[tot].Y2=m[Y2[i]],s[tot].flag=,tot++;

            s[tot].x=X2[i],s[tot].Y1=m[Y1[i]],s[tot].Y2=m[Y2[i]],s[tot].flag=-,tot++;

        }

        sort(s,s+tot,cmp);

        ans=;

        build(,k,);

        for(int i=; i<tot; i++)

        {

            int sum1=segTree[].len;

            update(s[i].flag,s[i].Y1+,s[i].Y2,,k,);

            int sum2=segTree[].len;

            ans=ans+abs(sum2-sum1);

        }

        lsh2();

        tot=;

        for(int i=; i<=n; i++)

        {

            s[tot].x=Y1[i],s[tot].Y1=m[X1[i]],s[tot].Y2=m[X2[i]],s[tot].flag=,tot++;

            s[tot].x=Y2[i],s[tot].Y1=m[X1[i]],s[tot].Y2=m[X2[i]],s[tot].flag=-,tot++;

        }

        sort(s,s+tot,cmp);

        build(,k,);

        for(int i=; i<tot; i++)

        {

            int sum1=segTree[].len;

            update(s[i].flag,s[i].Y1+,s[i].Y2,,k,);

            int sum2=segTree[].len;

            ans=ans+abs(sum2-sum1);

        }

        printf("%d\n",ans);

    }

    return ;

}