HDU 4533 웨 이 비 고양이 시리즈-이불 말리 기

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=4533
제목:첫 번 째 상한 선 에서 약간의 사각형 을 제시 합 니 다.지금 몇 가지 질문 을 드 리 겠 습 니 다.매번 질문 할 때마다 정수 t 를 드 리 고(0,0)에서(t,t)범위 의 사각형 면적 과.
사고방식:참고:http://blog.csdn.net/wh2124335/article/details/8739097。계산 을 통 해 다음 과 같은 알고리즘 을 얻 을 수 있 습 니 다.
입력 문의 t
sum=0
모든 사각형 의 네 개의 정점 을 옮 겨 다 닌 다.
   이 정점 이(0,0)-(t,t)범위 내 에 있다 면
    {
          현재 정점 이 사각형 의 왼쪽 상단 이나 오른쪽 하단 에 있 는 점 이 라면 sum-=[(t,t)와 이 점 이 형 성 된 사각형 의 면적]
         그렇지 않 으 면 sum+=[(t,t)와 이 점 이 형 성 된 사각형 의 면적]
    }
복귀 sum
다음은 최적화:현재 점 좌표 가(x,y)라 고 가정 하면 S=(t-x)*(t-y).우 리 는 그것 을 전개 할 수 있다.S=t*t-t(x+y)+xy.따라서 상식 을 세 부분 으로 나 누 어 화 해 를 구 할 수 있다.그러면 우 리 는 모든 사각형 왼쪽 아래 와 오른쪽 위 에 있 는 점 을 한 조 a 로 나 눌 수 있다.그러면 결 과 는 sigma[a 에서(t,t)범위 내의 점 과 T 가 형 성 된 사각형 면적]-sigma[b 가(t,t)범위 내의 점 과 T 가 형 성 된 사각형 면적]으로 쓸 수 있다. a,b 의 점 을 각각 max(x,y)로 정렬 합 니 다.매번 질문 t 에 대해 우 리 는 2 분 동안 a,b 의 위치 n,m(즉 max(x,y)가 t 의 가장 큰 아래 표 시 를 초과 하지 않 는 다 는 것 을 찾 았 다.답 은:
Sum(Sa)-Sum(Sb)
=sigma[t*t-t*(x+y)+xy](a 중점)-sigma[t*t-t*(x+y)+xy](b 중점)
=[sigma(t*t)-sigma(x+y)+sigma(xy)](a 중점)-[sigma(t*t)-sigma(x+y)+sigma(xy)](b 중점)
그리고 전 i 항 을 미리 처리 하면 됩 니 다.

struct node

{

    int x,y;



    node(){}

    node(int _x,int _y)

    {

        x=_x;

        y=_y;

    }



    int get()

    {

        return max(x,y);

    }

};



node a[N],b[N];

i64 s1[N],s2[N],f1[N],f2[N];

int n,m;



int T;



int cmp(node a,node b)

{

    return a.get()<b.get();

}





int find(node a[],int t)

{

    if(a[1].get()>t) return 0;

    if(a[2*n].get()<=t) return 2*n;

    int low=1,high=2*n,mid;

    while(low<=high)

    {

        mid=(low+high)>>1;

        if(a[mid].get()<=t) low=mid+1;

        else high=mid-1;

    }

    while(high<=2*n&&a[high].get()<=t) high++;

    return high-1;

}



void deal()

{

    int i,x,y;

    i64 ans,p,q,t;

    RD(m);

    FOR1(i,m)

    {

        RD(t);

        x=find(a,t);

        y=find(b,t);

        p=x*t*t-s1[x]*t+f1[x];

        q=y*t*t-s2[y]*t+f2[y];

        ans=p-q;

        PR(ans);

    }

}



int main()

{

    RD(T);

    while(T--)

    {

        RD(n);

        int x1,y1,x2,y2,i;

        FOR1(i,n)

        {

            RD(x1,y1,x2,y2);

            a[i*2-1]=node(x1,y1);

            a[i*2]=node(x2,y2);

            b[i*2-1]=node(x1,y2);

            b[i*2]=node(x2,y1);

        }

        sort(a+1,a+2*n+1,cmp);

        sort(b+1,b+2*n+1,cmp);

        FOR1(i,2*n)

        {

            s1[i]=s1[i-1]+a[i].x+a[i].y;

            s2[i]=s2[i-1]+b[i].x+b[i].y;

            f1[i]=f1[i-1]+(i64)a[i].x*a[i].y;

            f2[i]=f2[i-1]+(i64)b[i].x*b[i].y;

        }

        deal();

    }

    return 0;

}