线段树专题 - Blog

POJ 3264

题意：给出一串的数字，然后给出一个区间a b，输出从a到b的最大的数和最小的数的差

解题思路：直接跑两次query，一次查询最小，一次查询最大即可。

POJ 2528

题意：n（n<=10000)个人依次贴海报,给出每张海报所贴的范围li，ri（1<=li<=ri<=10000000)，求出最后还能看见多少张海报。

解题思路：离散化+线段树。

离散化部分：

如下面的例子（题目的样例），因为单位1是一个单位长度，将下面的

1 2 3 4 6 7 8 10

— — — — — — — —

1 2 3 4 5 6 7 8

离散化 X[1] = 1; X[2] = 2; X[3] = 3; X[4] = 4; X[5] = 6; X[7] = 8; X[8] = 10

于是将一个很大的区间映射到一个较小的区间之中了，然后再对每一张海报依次更新在宽度为1~8的墙上(用线段树），最后统计不同颜色的段数。

但是只是这样简单的离散化是错误的，

如三张海报为：1~10 1~4 6~10

离散化时 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10
第一张海报时：墙的1~4被染为1；
第二张海报时：墙的1~2被染为2，3~4仍为1；
第三张海报时：墙的3~4被染为3，1~2仍为2。
最终，第一张海报就显示被完全覆盖了，于是输出2，但实际上明显不是这样，正确输出为3。

新的离散方法为：在相差大于1的数间加一个数，例如在上面1 4 6 10中间加5（算法中实际上1，4之间，6，10之间都新增了数的）

X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 5, X[ 4 ] = 6， X[ 5 ] = 10

这样之后，第一次是1~5被染成1；第二次1~2被染成2；第三次4~5被染成3

最终，1~2为2，3为1，4~5为3，于是输出正确结果3。

这里不用map，用二分查找找到离散后的编号即可。

线段树部分：

把海报的编号当成lazy标记，如果访问了某个区间，则lazy标记更新，update和query的时候都要标记下传，本区间的lazy标记归零。

HDU 4027

题意：给定100000个数，两种操作，0 i j表示将i j这段的数字都开根号（向下取整），1 i j表示查询i j之间的所有值的和（所有的和都不超过64位）。

解题思路：注意到值为1之后就不用再开根号了，注意这个剪枝即可，还有注意开long long。

HDU 1540

题意：D代表破坏村庄，R代表修复最后被破坏的那个村庄，Q代表询问包括x在内的最大连续区间是多少。

解题思路：区间合并问题。设置lsum[n],rsum[n]分别表示区间左端连续村庄个数,区间右端连续村庄个数。

注意query函数的写法：

int query(int loc,int id)   //区间查询
{
    int l=node[id].left;
    int r=node[id].right;
    if(l==r)return 0;
    int m=(l+r)>>1;
    if(loc>=m-node[id<<1].rsum+1&&loc<=m+node[id<<1|1].lsum)
       return node[id<<1].rsum+node[id<<1|1].lsum;
    if(loc<=m)return query(loc,id<<1);
    else return query(loc,id<<1|1);
}

HDU 3974

题意：一棵树的结构，父节点是老板，子节点是员工，每次给父节点分配的任务，立即会下分到他所有的子节点，有更新和查询命令。

解题思路：以样例为例子：

用dfs将结点重新编号，对于每个结点，保存st和ed，分别表示自己的编号和最后儿子的编号，使其连续，然后映射到线段树上，对于T操作就是对于st[i]到ed[i]的区间修改，对于C操作就是单点查询。

HDU 1542

题意：矩形面积并。

解题思路：

http://www.cnblogs.com/KonjakJuruo/p/6024266.html

http://blog.csdn.net/kirito_acmer/article/details/45918499

HDU 4578

题意：

给一个数组，初始值为零，有四种操作

“1 x y c”,代表把区间 [x,y] 上的值全部加c

“2 x y c”,代表把区间 [x,y] 上的值全部乘以c

“3 x y c” 代表把区间 [x,y]上的值全部赋值为c

“4 x y p” 代表求区间 [x,y] 上值的p次方和1<=p<=3

解题思路：

lazy标记用ax+b即可。注意细节即可。

HDU 4614

题意：

有n个花瓶，标号0 ~ n−1。m个操作，

‘1AF′，表示从A位置开始插F朵花，遇到有花的花瓶跳过。到最后一个花瓶都还有花剩余，丢弃剩下的花。

‘2AB′，表示将区间[A,B]内的花瓶全部清空。(A≤B)

对于每个1操作，输出第一个和最后一个插花的位置，如果一朵花都插不了，输出‘Can not put any one.’；对于每个2操作，输出区间[A,B]内被清空的花瓶的数量。

解题思路：

线段树+二分。

令num(i,j)为区间[i,j]的空花瓶数。
对于一个1操作，首先判一下num(A,n)是否大于0。之后，因为区间[A,n]的空花瓶数是单调不递减的，所以可以通过二分查找到一个最小的位置L，使得num(A,L)==1，则此时的L就是第一个插花的位置；同样二分找到一个最小的位置R，使得num(A,R)==min(F,num(A,n))，则此时的R就是最后一个插花的位置。
对于一个2操作，直接询问区间[A,B]的空花瓶数，拿总数一减，输出。

二分的写法：

int bin_search(int loc,int num)
{
    int l=loc,r=n-1;
    int res;
    while(l<=r)
    {
        int m=(l+r)>>1;
        ans=0;
        query2(loc,m,1);
        if(ans>=num)
        {
            res=m;
            r=m-1;
        }
        else l=m+1;
    }
    return res;
}