HDU 5200 Trees (正向线段树,逆向并查集) - CSDN博客

原题链接:Trees(hdoj/hdu5200) ?
文章价值(3) ?
阅读数(159) ?

[原]HDU 5200 Trees (正向线段树,逆向并查集)

2015-4-5阅读94 评论0


传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5200

Trees

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)


Problem Description
Today CodeFamer is going to cut trees.There are?N?trees standing in a line. They are numbered from?1?to?N. The tree numbered?i?has height?hi. We say that two uncutted trees whose numbers are?x?and?y?are in the same block if and only if they are fitting in one of blow rules:

1)x+1=y or y+1=x;

2)there exists an uncutted tree which is numbered?z, and?x?is in the same block with?z, while?y?is also in the same block with?z.

Now CodeFamer want to cut some trees whose height is not larger than some value, after those trees are cut, how many tree blocks are there?
?

Input
Multi test cases (about?15).

For each case, first line contains two integers?N?and ? ?Q?separated by exactly one space, N indicates there are?N?trees,?Q?indicates there are?Q?queries.

In the following?N?lines, there will appear?h[1],h[2],h[3],,h[N]? ? ? ? which indicates the height of the trees.

In the following?Q?lines, there will appear?q[1],q[2],q[3],,q[Q]? ? ? ? ? which indicates CodeFamer’s queries.

Please process to the end of file.

[Technical Specification]

1≤??N , ?Q ? ???50000

0h[i]1000000000(109)

0q[i]1000000000(109)
?

Output
For each?q[i], output the number of tree block after CodeFamer cut the trees whose height are not larger than?q[i].
?

Sample Input
3 2 5 2 3 6 2
?

Sample Output
0 2
Hint
In this test case, there are 3 trees whose heights are 5 2 3. For the query 6, if CodeFamer cuts the tree whose height is not large than 6, the height form of left trees are -1 -1 -1(-1 means this tree was cut). Thus there is 0 block. For the query 2, if CodeFamer cuts the tree whose height is not large than 2, the height form of left trees are 5 -1 3(-1 means this tree was cut). Thus there are 2 blocks.



这题后来看到有人用线段树去做,官方给的亚博体育网页版登录也是正向离线查询的线段树,感觉这个思路从理解到实现上都相对复杂,所以共享一下自己的解法。


首先这题的题意是给你一排树,每棵树的高度也给你。接下来若干次询问,每次询问砍掉高度小于等于X的树之后,剩下的树分成几块(若干棵树之间如果没有被砍掉的树,即视为连成了一块)


那么根据题意,很容易就被绕到砍树里面,于是就假定所有树都活着,然后一棵一棵地去砍,官方亚博体育网页版登录也是这么给的。


但是这里倒过来想一想,砍树反过来就是长树,如果最开始假定是一块平地,那么就好做得多。

首先把树的高度和所有询问分别从大到小排序,然后对于每次询问,让高度大于它的树全部长出来,每次长树如果这棵树两边的树都没长,自然分块加一,如果两边的树都涨了,则分块减一,如果只有一边长了,那么分块数不变。

最后将记录好的查询结构体排回原来的顺序输出即可。


下面贴代码。显然是比线段树要简单得多的。


#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define M 1000005  //10^6
#define eps 1e-8
#define LL long long
#define moo 1000000007
#define INF -999999999
using namespace std;
struct aa
{
    int id;
    int num;
    int ans;
}a[100000];//记录查询的结构体
struct bb
{
    int id;
    int num;
}b[100000];//记录树高度的结构体
int vis[100000];//记录第i个点的树有没有长出来
bool cmp1(bb x,bb y)
{
    return x.num>y.num;
}
bool cmp2(aa x,aa y)
{
    return x.num>y.num;
}
bool cmp3(aa x,aa y)
{
    return x.id=b[nowb].num)
            {
                a[nowa].ans=ans;
                nowa++;
            }//当前查询比下一个长的树高,查询结果即为当前长着的树的分块数
            else
            {
                for(;b[nowb].num>a[nowa].num&&nowb<=n;nowb++)
                {
                    int p=b[nowb].id;
                    vis[p]=1;
                    if(vis[p-1]==1&&vis[p+1]==1)
                        ans--;
                    else if(vis[p-1]==0&&vis[p+1]==0)
                        ans++;
                }
                //将此时所有能长的树都长出来
            }
        }
        //处理一下所有树都长完之后剩余的查询
        if(nowb==n+1)
            for(;nowa<=m;nowa++)
                a[nowa].ans=ans;
        //讲查询排回原序并输出
        sort(a+1,a+m+1,cmp3);
        for(int i=1;i<=m;i++)
            printf("%d\n",a[i].ans);
    }
    return 0;
}


查看评论
更多评论(0)




(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: