# POJ PKU 2528 Mayor's posters 解题报告

题目链接: <http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=2528>

这题又是线段树+离散化

慢慢的对离散化有点感觉了,但是这题我还是错了3次

题目大意是一层一层地叠板子,问最后能看到几块

输入是板子的开始和结束位置

由于输入的是闭区间线段开始我就构造闭区间线段的线段树,但是后来发现很多问题,

比如构造线段树的时候有区间1-4-->1-2+3-4.如果1映射到位置1,2映射到4,3映射到8,4映射到12,那么5,6,7三个点就丢失了

所以后来改成了半开半闭区间,结果还是出了点问题,最后开成完全开区间才AC

也就是线段树表示两个端点,,比如位置1两端的端点是0和1,那么测试数据就有

(0 4)

(1 6)

(7 10)

(2 4)

(6 10)

五个开区间

然后在旧时一般的离散化+线段树了

贴代码:

```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 10005
struct node
{
    long l,r,h;
};
long buildTree(long l,long r,long pos);
void addHeight(long l,long r,long pos,long h);
void dealData(long &n,long pos);
node old[MAXN],newT[MAXN * 10];
bool isShowed[MAXN];
long tn,num,index[MAXN * 2];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t --)
    {
        memset(old,0,sizeof(old));
        memset(newT,0,sizeof(newT));
        memset(index,0,sizeof(index));
        memset(isShowed,false,sizeof(isShowed));
        int i,j;
        num = tn = 0;
        scanf("%d",&n);
        for(i = 0 ; i < n ; i ++)
            scanf("%ld %ld",&old[i].l , &old[i].r) ,old[i].h = i + 1
            , index[num ++] = old[i].l - 1 , index[num ++] = old[i].r;
        sort(index , index + num);
        j = 1;
        for(i = 1 ; i < num ; i ++)
            if(index[i] != index[j - 1])
                index[j ++] = index[i];
        index[j] = index[j - 1] + 1;
        num = j;
        buildTree(0,num - 1, 1);
        for(i = 0 ; i < n ; i ++)
            addHeight(old[i].l - 1 , old[i].r ,1, old[i].h);
        dealData(tn , 1);
        j = 0;
        for(i = 0 ; i < MAXN ; i ++)
            j += isShowed[i]?1:0;
        printf("%d\n",j);
    }
    return 0;
}

long buildTree(long l,long r,long pos)
{
    newT[pos].l = l;
    newT[pos].r = r;
    newT[pos].h = 0;
    long mid = (l + r) >> 1;
    tn = (pos > tn)? pos : tn;
    if(r > l + 1)
        return 1 + buildTree(l , mid, 2 * pos) + buildTree(mid , r, 2 * pos + 1);
    else
        return 1;
}
void addHeight(long l,long r,long pos,long h)
{
    if(l == index[newT[pos].l] && r == index[newT[pos].r])
    {
        newT[pos].h = h;
        return;
    }
    if(newT[pos].l >= newT[pos].r)
        return;
    long mid = (newT[pos].l + newT[pos].r) >> 1;
    if(newT[pos].h)
    {
        newT[2 * pos].h = newT[pos].h;
        newT[2 * pos + 1].h = newT[pos].h;
        newT[pos].h = 0;
    }
    if(index[mid] >= r)
        addHeight(l,r,2 * pos, h);
    else if(index[mid] <= l)
        addHeight(l,r,2 * pos + 1, h);
    else
    {
        addHeight(l,index[mid],2 * pos, h);
        addHeight(index[mid],r,2 * pos + 1, h);
    }
}
void dealData(long &n,long pos)
{
    if(newT[pos].h)
    {
        isShowed[newT[pos].h] = true;
        return;
    }
    if(2 * pos <= tn)
        dealData(n,2 * pos);
    if(2 * pos + 1 <= tn)
        dealData(n,2 * pos + 1);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.owent.net/2009/65.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.