POJ 2528 Mayor's posters （线段树+离散化）

链接：http://poj.org/problem?id=2528

题意：一面特别特别特别长的墙要贴相对非常短的海报，按给出顺序贴，问贴完后最后还能看见那几张海报。

思路：不能用最基本的线段树，因为墙实在太长了，会MLE。用离散化的思想。就是把所有海报的端点从小到大依次标记为1,2...M。（需要去重，所以不一定是2*N个点），其他的与基本线段树相同。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 10005
#define maxm
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
struct Line
{
    int l,r;
    int per;
    int mid()
    {
        return (l+r)>>1;
    }
}line[maxn*8];
int P[maxn][2],N[maxn*2],A[10000005];
int build_tree(int l,int r,int step)
{
    line[step].l=l;
    line[step].r=r;
    line[step].per=0;
    if(l==r)
        return 0;
    build_tree(l,line[step].mid(),step<<1);
    build_tree(line[step].mid()+1,r,step<<1|1);
}
int update(int l,int r,int step)
{
    if(line[step].per)
    return 0;
    if(line[step].l==l&&r==line[step].r)
    {
        line[step].per=1;
        return 1;
    }
    int res=0;
    if(line[step].mid()>=r)
    res=update(l,r,step<<1);
    else if(line[step].mid()<l)
    res=update(l,r,step<<1|1);
    else
    {
        res=update(l,line[step].mid(),step<<1)|update(line[step].mid()+1,r,step<<1|1);
    }
    if(line[step<<1].per&&line[step<<1|1].per)
    line[step].per=1;
    return res;
}
int init()
{
    memset(P,0,sizeof(P));
    memset(N,0,sizeof(N));
    memset(A,0,sizeof(A));
    memset(line,0,sizeof(line));
}
int main()
{
    int tot,tt;
    scanf("%d",&tot);
    for(int ii=0;ii<tot;ii++)
    {
        init();
        int j=0;
        scanf("%d",&tt);
        for(int i=0;i<tt;i++)
        {
            scanf("%d%d",&P[i][0],&P[i][1]);
            N[j++]=P[i][0];
            N[j++]=P[i][1];
        }
        sort(N,N+j);
        j=unique(N,N+j)-N;//unique函数返回非重复数的最后一个的尾地址
        for(int i=0;i<j;i++)
        {
            A[N[i]]=i;
        }
        build_tree(0,j-1,1);
        int ans=0;
        for(int i=tt-1;i>=0;i--)
        {
            if(update(A[P[i][0]],A[P[i][1]],1))
            ans++;
        }
        printf("%d\n",ans);
    }
}

POJ 2528 Mayor's posters （线段树+离散化）

原文：http://blog.csdn.net/ooooooooe/article/details/19779683