`
yzmduncan
  • 浏览: 330345 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

数据结构之——线段树(2)

线段树 Lazy操作 矩形面积并/交 矩形框住最多点 
阅读更多

    学习了上一节线段树的基本操作之后，再用例题详细讨论线段树的Lazy操作的精髓。

1. 矩形面积并。POJ1389 / HDU1542

    题意：矩形面积并是给出n个矩形(边都平行于x轴或y轴)，这些矩形可能会相互重合，求出总的覆盖面积。

    分析： 通过画图并观察，在x轴方向扫描这些矩形，发现只需要记录前面边的重合（有效）长度，比如有两条边，分别为[2,4], [3,8]，那么他们的有效长度为6。矩形的左边(入边)为1，右边(出边)为-1。现在就需要如何维护这些线段的有效长度了。可以想到用线段树来维护，因为它的插入和删除都是logn级别的。

    解：a. 将点y坐标升序排序，离散化并去重，构建线段树，注意叶子节点区间长度为1。

          b. 将扫描线(矩形的左右边)按x升序排序，依次插入线段树中，维护有效距离。

          c. 面积 += 整个区间的有效长度 * (下一条扫描线的x坐标-本条线的x坐标)。

    可见，如何维护有效距离是本问题的关键。

    一种简单的方法是每次更新到叶子节点，但这样发挥不出线段树的优势，没有用到lazy思想。

    可以设置两个变量len和cover，len表示该区间的有效长度，cover代表该区间是否被完全覆盖(0表示未被完全覆盖，>=1表示被完全覆盖)。当cover>=1时，len=y[r]-y[l]；否则，如果是叶子节点，则len=0；否则，len=len[l]+len[r]。

    实质：区间累加+统计区间有效长度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define LL(x) ((x)<<1)
#define RR(x) ((x)<<1|1)
const int N = 1005;

int yy[N*2],range;    //离散y
struct Line
{
    int x;
    int y_up;
    int y_down;
    int cover;  //入边为1，出边为-1
}line[N*2];

struct Seg_Tree
{
    int left;
    int right;
    int cover;  //完全覆盖为>=1，未被完全覆盖为0
    int len;    //该段被覆盖的有效长度
    int calmid()
    {
        return (left+right)>>1;
    }
}tree[N*8];

bool cmp(Line a, Line b)
{
    return a.x < b.x;
}

void build(int left, int right, int idx)
{
    tree[idx].left = left;
    tree[idx].right = right;
    tree[idx].cover = 0;
    tree[idx].len = 0;
    if(left+1==right)
        return;
    int mid = (left+right)>>1;
    build(left,mid,LL(idx));
    build(mid,right,RR(idx));
}

int BiSearch(int v)
{
    int low = 0;
    int high = range;
    while(low<=high)
    {
        int mid = (low+high)>>1;
        if(yy[mid]==v)
            return mid;
        if(yy[mid] < v)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low;
}

void updateLen(int i)
{
    if(tree[i].cover)
        tree[i].len = yy[tree[i].right] - yy[tree[i].left];
    else if(tree[i].left + 1 == tree[i].right)
        tree[i].len =  0;
    else
        tree[i].len = tree[LL(i)].len + tree[RR(i)].len;
}

//更新段[a,b]
void update(int a, int b, int c, int idx)
{
    if(tree[idx].left==a && tree[idx].right == b)
    {
        tree[idx].cover += c;
        updateLen(idx);
        return ;
    }
    int mid = tree[idx].calmid();
    if(b <= mid)
        update(a,b,c,LL(idx));
    else if(a >= mid)
        update(a,b,c,RR(idx));
    else
    {
        update(a,mid,c,LL(idx));
        update(mid,b,c,RR(idx));
    }
    updateLen(idx);
}

int main()
{
    int i,j;
    int x1,y1,x2,y2;
    while(scanf("%d %d %d %d",&x1,&y1,&x2,&y2)!=EOF&&x1!=-1&&y1!=-1&&x2!=-1&&y2!=-1)
    {
        i = 0;
        do
        {
            line[i].x = x1;
            line[i].y_down = y1;
            line[i].y_up = y2;
            line[i].cover = 1;
            yy[i] = y1;
            i++;
            line[i].x = x2;
            line[i].y_down = y1;
            line[i].y_up = y2;
            line[i].cover = -1;
            yy[i] = y2;
            i++;
        }while(scanf("%d %d %d %d",&x1,&y1,&x2,&y2)&&x1!=-1&&y1!=-1&&x2!=-1&&y2!=-1);
        sort(line,line+i,cmp);
        sort(yy,yy+i);
        range = 0;
        for(j = 0; j < i; j++)
        {
            if(j==0||yy[j]!=yy[j-1])
                yy[range++] = yy[j];
        }
        range--;
        build(0,range,1);
        int result = 0;
        for(j = 0; j < i-1; j++)
        {
            int a = BiSearch(line[j].y_down);
            int b = BiSearch(line[j].y_up);
            update(a,b,line[j].cover,1);
            result += tree[1].len*(line[j+1].x - line[j].x);
        }
        printf("%d\n",result);
    }
    return 0;
}
/*
0 1 3 4
2 0 4 3
1 2 5 5
-1 -1 -1 -1
*/

 

 

 

2. 矩形面积交。HDU1255

    类似于矩形面积并，用扫描线+线段树求解。这里需要设置两个变量one_len和more_len，分别用来表示覆盖次数>=1次的长度和>=2次的长度。

    如果cover>=2，one_len=more_len=y[r]-y[l]；

    如果cover==1，one_len=y[r]-y[l]，more_len=one_len[l] + one_len[r]；

    如果cover==0，one_len=one_len[l]+one_len[r]，more_len=more_len[l]+more_len[r]。

void setLen(int idx)
{
    int r = tree[idx].right;
    int l = tree[idx].left;
    if(tree[idx].cover > 1)
        tree[idx].one_len = tree[idx].more_len = yy[r] - yy[l];
    else if(tree[idx].cover == 1)
    {
        tree[idx].one_len = yy[r] - yy[l];
        if(l+1 == r)
            tree[idx].more_len = 0;
        else
            tree[idx].more_len = tree[LL(idx)].one_len + tree[RR(idx)].one_len;
    }
    else
    {
        if(l+1 == r)
            tree[idx].one_len = tree[idx].one_len = 0;
        else
        {
            tree[idx].one_len = tree[LL(idx)].one_len + tree[RR(idx)].one_len;
            tree[idx].more_len = tree[LL(idx)].more_len + tree[RR(idx)].more_len;
        }
    }
}

 

 

 

3. 一个矩形最多能够框多少个点（边界点不算）。POJ2482 / HDU4007

    题意：二维平面上有n个点，给出一个宽为w高为h的矩形，矩形可以任意平移，问这个矩形最多能够框住多少个点。

    分析：这个问题看似没有思路，不妨将点看做一个以它为左下顶点的w*h的矩形。矩形左边为1，右边为-1。是不是有点像上面的形式了？其实这里是将一颗点分为两点(x,y,1)和(x+w,y,-1)，这样，当我们不断插入点时，就相当于有一个矩形在从左向右移动，因为碰到第一点总数+1，相当于框住了该点；碰到第二点是1+(-1)=0，相当于没有框住点。每次插入时，由于x固定，而y不固定，该点在y轴上影响到的范围为[y,y+h)，注意这里是开区间，因为边界的点不算在内。同时记录最大值。

   关键问题：如何实现区间累加和最值的维护。用两个变量add和max：add代表当前加的数的和，max记录该区间的最值。每次进行更新时，若当前节点add!=0，就将该节点的add值传递到左右孩子节点上，自己的add重新赋为0。整个区间的最值为左右孩子区间的较大者。

    实质：区间累加+区间最值

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL(x) ((x)<<1)
#define RR(x) ((x)<<1|1)
typedef __int64 int64;
const int N = 10005;

int n,w,h;

struct Point
{
    int64 x,y;
    int64 v;
    bool operator <(const Point &p) const
    {
        if(x != p.x)
            return x < p.x;
        return v < p.v;
    }
}point[N*2];
int64 y[N*2];

struct Seg_Tree
{
    int left;
    int right;
    int64 max;  //当前区间的max
    int64 add;  //记录当前加的数和
    int calmid()
    {
        return (left+right)>>1;
    }
}tt[N*8];

bool cmp(const int64& a, const int64& b)
{
    return a < b;
}

int64 max(int64 a, int64 b)
{
    return a > b ? a : b;
}

void build(int left, int right, int idx)
{
    tt[idx].left = left;
    tt[idx].right = right;
    tt[idx].add = tt[idx].max = 0;
    if(left == right)
        return;
    int mid = (left+right)>>1;
    build(left,mid,LL(idx));
    build(mid+1,right,RR(idx));
}

int BinSearch(int aim, int low, int high)
{
    while(low <= high)
    {
        int mid = (low+high)>>1;
        if(y[mid] == aim)
            return mid;
        if(y[mid] < aim)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

void update(int left, int right, int value, int idx)
{
    if(tt[idx].left>=left&&tt[idx].right<=right)
    {
        tt[idx].add += value;
        tt[idx].max += value;
        return;
    }
    if(tt[idx].add != 0)
    {
        tt[LL(idx)].add += tt[idx].add;
        tt[RR(idx)].add += tt[idx].add;
        tt[LL(idx)].max += tt[idx].add;
        tt[RR(idx)].max += tt[idx].add;
        tt[idx].add = 0;
    }
    int mid = tt[idx].calmid();
    if(left <= mid)
        update(left,right,value,LL(idx));
    if(right > mid)
        update(left,right,value,RR(idx));
    tt[idx].max = max(tt[LL(idx)].max, tt[RR(idx)].max);
}

int main()
{
    int i;
    while(scanf("%d %d %d",&n,&w,&h)!=EOF)
    {
        for(i = 0; i < n; i++)
        {
            scanf("%I64d %I64d %I64d",&point[i].x,&point[i].y,&point[i].v);
            y[i] = point[i].y;
            y[n+i] = point[i].y+h;
            point[n+i].x = point[i].x+w;
            point[n+i].y = point[i].y;
            point[n+i].v = -point[i].v;
        }
        n = n<<1;
        sort(y,y+n,cmp);
        sort(point,point+n);
        int k = 0;
        //unique如何使用
        for(i = 0; i < n; i++)
        {
            if(i==0 || y[i] != y[i-1])
                y[k++] = y[i];
        }
        k--;
        build(0,k,1);
        int64 result = -1;
        for(i = 0; i < n; i++)
        {
            int left = BinSearch(point[i].y, 0, k);
            int right = BinSearch(point[i].y+h, 0, k) - 1; //更新区间[y,y+h)
            if(left>right)
                swap(left,right);
            update(left,right,point[i].v,1);
            if(result < tt[1].max)
                result = tt[1].max;
        }
        printf("%I64d\n",result);
    }
    return 0;
}
/*
3 5 3
2 2 3
3 1 5
4 -2 4
8
*/

 

 

分享到：
| 数据结构之——线段树(1)
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    统计的力量——线段树全接触_张昆玮.pptx

    ### 统计的力量——线段树全接触 #### 引言 线段树作为一种高效的数据结构，在算法竞赛中尤其受到重视。它不仅适用于区间查询，还能处理动态更新问题，是解决许多复杂问题的关键工具之一。张昆玮老师的《统计的力量...

    线段树——在ACM中制胜的法宝

    线段树——在ACM中制胜的法宝 线段树是一种非常重要的数据结构，广泛应用于算法竞赛（ACM）和实际编程中。线段树可以高效地解决许多问题，如区间查找、区间更新、区间统计等。但是，对于线段树的理解和应用，需要对...

    线段树（模板+例题——郭神）

    线段树，有时也被称为区间树，是一种高效的数据结构，主要用于处理区间查询和区间更新的问题。它通过将一个大的区间划分为若干个较小的、互不重叠的子区间来实现这一功能。下面我们将详细介绍线段树的基本定义及其...

    线段树算法的Python实现及应用介绍

    内容概要：本文详细介绍了一种高级数据结构——线段树（Segment Tree），主要探讨了它的实现方法及其在区间查询与更新问题中的应用，包括具体实现的Python代码片段。 适合人群：对数据结构有基本认识的程序员或数据...

    线段树和树状数组——北京大学暑期课《ACM/ICPC竞赛训练》

    线段树是一种高效的数据结构，主要用于处理区间查询和区间更新问题。它通过将一个大的区间细分成若干个较小的不重叠的子区间来实现高效的区间操作。在计算机科学领域，尤其是在算法竞赛中，线段树是非常重要的工具之...

    线段树学习资料——清华大学讲义

    线段树是一种高效的数据结构，主要用于处理区间查询与更新问题，尤其在计算机科学中的算法设计中扮演着重要角色。清华大学的这份讲义是深入理解线段树的优质资源，它涵盖了线段树的基础理论、实现细节以及应用实例，...

    解决动态统计问题的两把利刃——剖析线段树与矩形切割_薛矛.ppt

    线段树是一种高效的数据结构，常用于解决动态统计问题，特别是在计算机科学和算法设计中。它的主要作用是在一组数据上支持快速的区间查询和修改。线段树通过将线段分解为更小的子线段并存储在二叉树结构中，能够实现...

    动态序列与动态树问题——浅谈几种常用数据结构_莫凡.pdf

    "动态序列与动态树问题——浅谈几种常用数据结构" 本文主要讨论了动态序列问题和动态树问题的解决方法，通过介绍了几种常用的平衡二叉树型数据结构来解决这些问题。动态序列问题是指在一个序列上执行一系列在线操作...

    线段树（一）——概念和应用

    线段树是一种高效的数据结构，广泛应用于解决与区间查询和修改相关的编程问题。在IT行业中，熟悉线段树是提高算法能力、优化代码性能的重要手段。这篇博客文章“线段树（一）——概念和应用”可能深入浅出地介绍了...

    线段树详解

    线段树是一种高效的数据结构，常被用于处理区间查询或更新的问题。它是一棵二叉树，其中每个节点代表一个特定的区间。具体来说： - **叶子节点**：代表一个单位区间，即形式为`[i, i]`的区间。 - **非叶子节点**：...

    线段树的论文,相当的好.不过是英文的,

    本文将深入探讨线段树的概念，特别是其动态版本——**动态线段树**（Dynamic Segment Tree），以及一种创新的数据结构——**并集复制结构**(Union-Copy Structure)，该结构为动态线段树的实现提供了坚实的基础。...

    ACM培训课件_提高篇_ACM算法讲座-线段树

    ### ACM培训课件知识点解析——线段树 #### 一、线段树概念与作用 线段树是一种高效的数据结构，用于存储和处理连续区间上的数据。它通过将区间分割成若干子区间，并在树的节点上存储这些子区间的相关信息，从而...

    刷题算法提高阶段-数据结构4

    本主题“刷题算法提高阶段-数据结构4”将着重于一个特殊的数据结构——线段树，它是处理区间查询和更新问题的有效工具。线段树是一种树形数据结构，用于高效地维护一段连续区间的信息，如区间求和、查找最值等操作。...

    高级数据结构——Advanced Data Structures电子书

    3. **正交范围查询结构**：用于多维空间中进行快速查询的数据结构，如矩形范围查询、线段树等。 4. **堆**：一种特殊形式的完全二叉树结构，常用于实现优先队列等。 5. **并查集（Union-Find Structures）**：一...

    线段树资料

    线段树是一种用于处理区间查询和更新问题的数据结构。它通过构建一颗具有特定结构的二叉树来实现对区间数据的有效管理和操作。具体而言，线段树能够高效地支持区间上的查询（如求和、最大值等）和更新操作（如增加、...

    Segment tree Beats!.pdf

    在计算机科学领域，特别是在算法设计与分析方面，**线段树**是一种非常重要的数据结构，它能够高效地支持区间查询和更新操作。本文档主要介绍了线段树在解决特定类型问题时的应用，特别是那些不再仅仅是NOIP级别（即...

Magicbox
Global site tag (gtag.js) - Google Analytics