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

Mayor's posters

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 41785		Accepted: 12164

Description

The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:

Every candidate can place exactly one poster on the wall.
All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
The wall is divided into segments and the width of each segment is one byte.
Each poster must completely cover a contiguous number of wall segments.

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall.

Input

The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers l_i and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= l_i <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered l_i, l_i+1 ,... , ri.

Output

For each input data set print the number of visible posters after all the posters are placed.

The picture below illustrates the case of the sample input.
线段树+离散化 poj 2528 Mayor's posters

Sample Input

Sample Output

4

给你n个区间，每个区间的颜色不同，后面区间的颜色会覆盖前面区间的颜色，n个区间覆盖完后，最后有多少种颜色
(log不写底数就相当于lg)
看题目数据范围，已经到10000000（10的七次方）
以下分析不考虑建树了，建树在此种思想中对复杂度影响很小

1.最容易想到的是直接暴搜改变每个点套线段树，时间复杂度是n*m’*(log(2*m)),其中m是区间中最大的数，即最长边界，m'是每个区间点的个数，这样直接写最坏的时间复杂度是10^4*10^7*7（大概值，log(2*m)可看作log(m)）。
2.接着我们考虑每次都是暴搜n个区间的每个点耗费太多时间，于是我们考虑将n个区间看成线段然后每次直接搜n条线段（将点连续化）,最后还要遍历底层一次,这样时间复杂度是n*(log(2*m))+n*m，最坏时间复杂度是10^4*7 + 10^4*10^7，会时间超限
3.然后我们容易看到m的取值过大影响了整个程序导致时间超限。于是我们考虑到将区间离散化来减少m的值。离散后我们得到m最大为n+1，所以最后的遍历+暴搜时间复杂度是 n*(log(2*n+2))+n*(n+1)，最坏时间复杂度是10^4*4 + 10^4*10^4,大约在10^8左右可以过这一个题目了

来讲下怎么离散，我们来看三个区间，[1,10],[1,3],[6,10]，发现[3,6],[7,10]这些都是白白浪费掉的。我们完全可以把他们变成[1,7],[1,3],[5,7],这样该染的区间发生了变化颜色未变，对于最后的结果并没有影响却减少了要求的区间要枚举的点
离散化的方法
把所有边界值排序后得到(1,1,3,6,10,10)，然后我们用一个h结构体数组保存下所有的值，在将其根据左边界和右边界的比较一一加入到a数组中，最后对a数组进行线段树相关运算（具体实现过程看代码）

#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
#define ls (u<<1)
#define rs (u<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const int maxn = 10000010;
struct {
    int l,r;
} a[maxn];
struct Line {  //用于离散化，id表示在原来的那个区间，pos为0表示区间中的左边界,为1表示区间中的右边界
    int val,id,pos;
};
Line h[maxn << 2];
bool cmp( Line x, Line y ) {
    return x.val < y.val;
}
ll node[maxn << 2],vis[maxn << 2];
int color[maxn << 2];
void build( int u, int left, int right ) {
    if( left != right ) {
        int mid = ( left + right ) >> 1;
        build( ls, left, mid );
        build( rs, mid+1, right );
    }
    color[u] = 0; //所有结点的颜色初始化为0
}
void update( int u, int left, int right, int L, int R, int num ) {
    if( L == left && R == right ) { //如果区间相同则直接更改颜色值
        color[u] = num;
        return ;
    }
    if( color[u] && color[u] != num ) { //如果有颜色并且颜色值不同则把颜色值赋给儿子节点并且将自己置零
        color[ls] = color[u];
        color[rs] = color[u];
        color[u] = 0;
    }
    int mid = ( left + right ) >> 1;
    if( R <= mid ) { //要求的区间在左儿子
        update( ls, left, mid, L, R, num );
    } else if( mid < L ) { //要求的区间在右儿子
        update( rs, mid+1, right, L, R, num );
    } else { //两边都有要求的区间
        update( ls, left, mid, L, mid, num );
        update( rs, mid+1, right, mid+1, R, num );
    }
}
int query( int u,int left, int right ) {
    if( color[u] ) {
        if( !vis[color[u]] ) {
            vis[color[u]] = 1;
            return 1;
        }
        return 0;
    }
    if( left == right ) {
        return 0;
    }
    int mid = ( left + right ) >> 1;
    return query( ls, left, mid ) + query( rs, mid+1, right );
}
int main(){
    int T;
    scanf("%d",&T);
    for( int t = 1; t <= T; t ++ ) {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++) {
            scanf("%d%d",&a[i].l,&a[i].r);

            h[2*i].val = a[i].l;
            h[2*i].id = i;
            h[2*i].pos = 0;

            h[2*i+1].val = a[i].r;
            h[2*i+1].id = i;
            h[2*i+1].pos = 1;
        }
        //离散化过程
        sort(h,h+2*n,cmp);
        int last = -1, total = 0;
        for(int i=0; i<2*n; i++ ) {
            if( h[i].val != last ) {
                if( h[i].val - last == 1 || !total ) { //区分相邻与不相邻情况
                    total ++;
                } else {
                    total += 2;
                }
                if( h[i].val != total ) {
                    if( h[i].pos ) {
                        a[h[i].id].r = total;
                    } else {
                        a[h[i].id].l = total;
                    }
                }
                last = h[i].val;
            } else {
                if( h[i].val != total ) {
                    if( h[i].pos ) {
                        a[h[i].id].r = total;
                    } else {
                        a[h[i].id].l = total;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++) {
            vis[i] = 0;
        }
        build( 1, 1, total );
        for(int i=0;i<n;i++) {
            //printf("i:%d,l:%d,r:%d
",i,a[i].l,a[i].r);
            update( 1, 1, total, a[i].l, a[i].r, i+1 );
        }
        printf( "%d
" , query( 1, 1, total ) );
    }
    return 0;
}

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

相关推荐