hdu4052Adding New Machine(線段樹求矩形面積并)

題目請戳這裡

題目大意：給一個w*h的矩陣，給n個矩形，n個矩陣互不相交。再給一個1*m的矩形，要求與給定的n個矩形不相交，求能擺放的方案種數。

題目分析：w和h很大，n有50000，是以離散化+線段樹。因為要擺放的矩形是1*m的，是以這個矩形隻有2種姿勢：橫着or豎着。是以從左向右掃描一遍，求出空地的面積并，從上向下掃描一遍，求剩餘面積并相加即可。不過要對之前的n個矩形處理一下：對于第i個矩形，從左向右掃描的話，将此矩形的右界向右伸長m-1，因為從左向右是恒着掃描的，如果1*m的矩形要橫着放，那麼矩形i的右界的右邊m-1個格子顯然也是不能放的，豎直方向也是同理，下界向下伸長m-1，直到越界為止。一開始的話，大矩形左到右和上到下1~m-1這個範圍指派一個很大的數，因為無論何時，這段都是不能放矩形的。大矩形的左右界，上下界也作為一條掃描線友善些。

trick：當m為1的時候，水準豎直放都一樣，是以求出來的答案除2！

ps:比賽的時候以為是dp，竟然沒看出是道線段樹，簡直弱爆了。。。

pps:用線段樹寫個矩形面積并寫了一天，簡直弱爆了。。。

ppps:zoj竟然用不了__int64，太ws了，累覺不愛了。。。

詳情請見代碼：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 500005;
int hx[N + N],hy[N + N],nx,ny;
struct node
{
    int a,b,c,d;
}linex[N],liney[N];
int w,h,n,m;
int cmp(struct node a,struct node b)
{
    return a.a < b.a;
}
struct nd
{
    int len,cover;
};
struct sgt
{
    struct nd tree[N<<2];
    void init(int num,int s,int e)
    {
        tree[num].cover = tree[num].len = 0;
        if(s == e)
            return;
        int mid = (s + e)>>1;
        init(num<<1,s,mid);
        init(num<<1|1,mid + 1,e);
    }
    void insert(int num,int s,int e,int l,int r,int val,int dir)
    {
        if(s == e)
        {
            tree[num].cover += val;
            if(tree[num].cover)
            {
                if(dir)
                    tree[num].len = hx[e + 1] - hx[s];
                else
                    tree[num].len = hy[e + 1] - hy[s];
            }
            else
                tree[num].len = 0;
            return;
        }
        if(s == l && e == r)
        {
            if(tree[num].cover > 0 || val > 0)//少了val>0會T.....
            {
                tree[num].cover += val;
                if(tree[num].cover > 0)
                {
                    if(dir)
                        tree[num].len = hx[e + 1] - hx[s];
                    else
                        tree[num].len = hy[e + 1] - hy[s];
                }
                else
                    tree[num].len = tree[num<<1].len + tree[num<<1|1].len;
                return;
            }
        }
        int mid = (s + e)>>1;
        if(tree[num].cover)
        {
            tree[num<<1].cover += tree[num].cover;
            tree[num<<1|1].cover += tree[num].cover;
            if(dir)//再往下更新一層！！！
            {
                tree[num<<1].len = hx[mid + 1] - hx[s];
                tree[num<<1|1].len = hx[e + 1] - hx[mid + 1];
            }
            else
            {
                tree[num<<1].len = hy[mid + 1] - hy[s];
                tree[num<<1|1].len = hy[e + 1] - hy[mid + 1];
            }
            tree[num].cover = 0;
        }
        if(r <= mid)
            insert(num<<1,s,mid,l,r,val,dir);
        else
        {
            if(l > mid)
                insert(num<<1|1,mid + 1,e,l,r,val,dir);
            else
            {
                insert(num<<1,s,mid,l,mid,val,dir);
                insert(num<<1|1,mid + 1,e,mid + 1,r,val,dir);
            }
        }
        tree[num].len = tree[num<<1].len + tree[num<<1|1].len;
    }
}stx,sty;
int getx(int x)
{
    int l,r,mid;
    l = 1;r = nx;
    while(l <= r)
    {
        mid = (l + r)>>1;
        if(hx[mid] == x)
            return mid;
        else
        {
            if(hx[mid] > x)
                r = mid - 1;
            else
                l = mid + 1;
        }
    }
}
int gety(int x)
{
    int l,r,mid;
    l = 1;r = ny;
    while(l <= r)
    {
        mid = (l + r)>>1;
        if(hy[mid] == x)
            return mid;
        else
        {
            if(hy[mid] > x)
                r = mid - 1;
            else
                l = mid + 1;
        }
    }
}

int main()
{
    int i,j;
    int x1,x2,y1,y2;
    while(scanf("%d",&w) != EOF)
    {
        scanf("%d%d%d",&h,&n,&m);
        w ++;h ++;
        nx = ny = 1;
        linex[1].a = liney[1].a = 1;
        linex[1].b = liney[1].b = m;
        linex[1].c = h;liney[1].c = w;
        for(i = 2;i <= n + n;i += 2)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x2 ++;y2 ++;
            linex[i].a = x1;linex[i].b = y1;linex[i].c = y2 + m - 1;linex[i].d = 1;
            if(linex[i].c > h)
                linex[i].c = h;
            linex[i + 1].a = x2;linex[i + 1].b = y1;linex[i + 1].c = y2 + m - 1;linex[i + 1].d = -1;
            if(linex[i + 1].c > h)
                linex[i + 1].c = h;
            liney[i].a = y1;liney[i].b = x1;liney[i].c = x2 + m - 1;liney[i].d = 1;
            if(liney[i].c  > w)
                liney[i].c = w;
            liney[i + 1].a = y2;liney[i + 1].b = x1;liney[i + 1].c = x2 + m - 1;liney[i + 1].d = -1;
            if(liney[i + 1].c > w)
                liney[i + 1].c = w;
            hx[nx ++] = x1;hx[nx ++] = x2;hx[nx ++] = liney[i].c;
            hy[ny ++] = y1;hy[ny ++] = y2;hy[ny ++] = linex[i].c;
        }
        linex[i].a = w;liney[i].a = h;
        linex[i].b = liney[i].b = m;
        linex[i].c = h;
        liney[i].c = w;
        hx[nx ++] = 1;hx[nx ++] = w;hx[nx ++] = m;
        hy[ny ++] = 1;hy[ny ++] = h;hy[ny ++] = m;
        sort(linex + 1,linex + n + n + 3,cmp);
        sort(liney + 1,liney + n + n + 3,cmp);
        sort(hx + 1,hx + nx);
        sort(hy + 1,hy + ny);
        j = nx;
        nx = ny = 2;
        for(i = 2;i < j;i ++)
        {
            if(hx[i] != hx[i - 1])
                hx[nx ++] = hx[i];
            if(hy[i] != hy[i - 1])
                hy[ny ++] = hy[i];
        }
        nx --;ny --;
        stx.init(1,1,ny);
        sty.init(1,1,nx);
        int l,r;
        l = 1;r = gety(m) - 1;
        if(l <= r)
            stx.insert(1,1,ny,l,r,1000000,0);
        r = getx(m) - 1;
        if(l <= r)
            sty.insert(1,1,nx,l,r,1000000,1);
        __int64 ans = 0;
        for(i = 2;i <= n + n + 2;i ++)
        {
            ans += (__int64)(linex[i].a - linex[i - 1].a) * (h - 1 - stx.tree[1].len);
            ans += (__int64)(liney[i].a - liney[i - 1].a) * (w - 1 - sty.tree[1].len);
            l = gety(linex[i].b);r = gety(linex[i].c) - 1;
            stx.insert(1,1,ny,l,r,linex[i].d,0);
            l = getx(liney[i].b);r = getx(liney[i].c) - 1;
            sty.insert(1,1,nx,l,r,liney[i].d,1);
        }
        if(m == 1)
            ans /= 2;
        printf("%I64d\n",ans);
    }
    return 0;
}
/*
3 3 1 2
2 2 2 2
3 3 1 3
2 2 2 2
2 3 2 2
1 1 1 1
2 3 2 3
3 3 0 2
3 3 0 1
3 3 1 1
2 2 2 2
5 4 1 2
2 2 3 3
5 4 5 2
1 1 1 2
2 3 2 4
3 1 3 2
4 3 4 4
5 1 5 2
4 4 2 2
2 1 3 2
2 3 3 4
*/
//1453MS	12812K