poj 2528 Mayor's posters(离散化 + 线段树)

解题思路

题意：

那个城市里要竞选市长，然后在一块墙上可以贴海报为自己拉票，每个人可以贴连续的一块区域，后来帖的可以覆盖前面的，问到最后一共可以看到多少张海报。

 

思路：

       用到线段树，因为最多有10^6，建那么大的树肯定会爆空间和时间，所以想到要离散化，将每条线段的两端，就是海报的两头分开考虑，所有的端点放在一起非递减排序，去掉相同的，计算出有n个不同的点，编号从1到n，——这是离散化过程。然后建二叉树。更新的时候先二分查找那条线段两端的点的编号，然后在那棵建好的树上更新，遇到一样的节点就覆盖，如果线段在那个节点的子节点上，而且这个节点又被其他线段覆盖过，那么就要更新它的子节点，他自己改成不被覆盖的。最后计算结果那里要用个辅助数组，从根节点开始找被覆盖的节点，分别将不同的值放在数组里，最后看有几个结果就是几个。

 

还有一种方法是把节点离散化成可以根据他们的输入的顺序找到各自的编号。那样就不用二分查找，可是花的时间反而多了。可能离散化那里复杂度高了。

源程序

Memory: 2500K
Time: 110MS

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define N 20002

struct line
{
    int times;
    int left, right;

}lines[N * 6];

struct item
{
    int first;
    int last;
}temp[2 * N];

void create(int s, int t, int step)
{
    lines[step].left = s;
    lines[step].right = t;
    if(s == t)
        return ;
    int mid = ( lines[step].left + lines[step].right ) / 2;
    create(s, mid, step * 2);
    create(mid + 1, t, step * 2 + 1);
}

void update(int s, int t, int step, int i)
{
    if(t == lines[step].right && lines[step].left == s)
    {
        lines[step].times = i;
        return;
    }
    
    if(lines[step].times != 0 && lines[step].times != i)
    {
        lines[step * 2].times = lines[step].times;
        lines[step * 2 + 1].times = lines[step].times;
        lines[step].times = 0;
    }

    int mid = ( lines[step].left + lines[step].right) / 2;
    if(t <= mid)
    {
        update(s, t, step * 2, i);
    }
    else if(s > mid)
        update(s, t, step * 2 + 1, i);
    else
    {
        update(s, mid, step * 2, i);
        update(mid + 1, t, step * 2 + 1, i);
    }
}
int k, result;
int re[N*6];
void cal(int num)
{
    if(lines[num].times)
    {

        if(re[lines[num].times] != 1)
        {
            re[lines[num].times] = 1;
            result++;
        }
        return ;
    }
    cal(2 * num );
    cal(2 * num + 1);
}

int cmp(const void *p, const void *q)
{
    line *a = (line *)p;
    line *b = (line *)q;
    return a->times < b->times ? 1 : -1;
}

int cmp2(const void *p, const void *q)
{
    return (((struct item *)p)->first - ((struct item *)q)->first);
}

int main()
{
    int i, j;
    int t, n;
    int l[N], r[N];
    struct item *x, *y, xx, yy;

    freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        memset(temp, 0, sizeof(temp));
        for(i=1, k=0; i<=n; i++)
        {
            scanf("%d%d", &l[i], &r[i]);
            temp[++k].first = l[i];
            temp[++k].first = r[i];
        }

        /*离散化*/
        qsort(temp+1, n * 2, sizeof(temp[0]), cmp2);
        i=1;
        k=0;
        while(1)
        {
            if(i > n * 2)
                break;
            k++;
            temp[k].first = temp[i].first;
            temp[k].last = k;
            while(temp[i+1].first == temp[i].first)
                i++;
            i++;
        }
    
        memset(lines, 0, sizeof(lines));
        create(1, k, 1); //建树


        for(i=1; i<=n; i++)
        {
            xx.first = l[i];
            yy.first = r[i];
            x = (struct item *)bsearch(&xx, temp+1, k, sizeof(temp[1]), cmp2);
            y = (struct item *)bsearch(&yy, temp+1, k, sizeof(temp[1]), cmp2);
            update(x->last, y->last, 1, i); //更新

        }
        result = 0;
        memset(re, 0, sizeof(re));
        cal(1); //计数

        
        printf("%d\n", result);
    }
    getch();
    return 0;
}