学习了上一节线段树的基本操作之后,再用例题详细讨论线段树的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
*/
分享到:
相关推荐
主要介绍线段树,并介绍其数据结构,还有相关的例题分析
线段树中的结点一般采取如下数据结构: 其中a,b分别表示线段的左端点和右端点,Left,Right表示左儿子和右儿子的编号。因此我们可以用一个一维数组来表示一棵线段树: Tree:array[1..Maxn] of TreeNode; ...
解决动态统计问题的两把利刃——剖析线段树与矩形切割
学习线段树很好的资料 希望能够对你有一定的帮助
Linqer 那点所谓的分布式(2)那点所谓的分布式——memcache 那点所谓的分布式——redis 树结构专题(5)6天通吃树结构—— 第五天 Trie树 6天通吃树结构—— 第四天 伸展树 6天通吃树结构—— 第三天 Treap树 6天通吃树...
目录 一.数论 4 1.阶乘最后非零位 4 2. 模线性方程(组) 4 3. 素数表 6 4. 素数随机判定(miller_rabin) 6 5. 质因数分解 7 6. 最大公约数欧拉函数 8 ...数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树
数据结构:数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树、复杂数据结构*、嵌套数据结构*等。 数据结构是本科必修课,不需要再从头开始复习。 需掌握:数据结构的八大分类 学习记录: 【C++ STL ...
陈 宏 -《数据结构的选择与算法效率——从IOI98试题PICTURE谈起》 来煜坤 -《把握本质,灵活运用——动态规划的深入探讨》 齐 鑫 -《搜索方法中的剪枝优化》 邵 铮 -《数学模型的建立、比较和应用》 石润婷 -...
3.3.1 线段树 3.3.2 Binary Indexed Tree 3.3.3 分桶法和平方分割 3.4 熟练掌握动态规划 3.4.1 状态压缩DP 3.4.2 矩阵的幂 3.4.3 利用数据结构高效求解 3.5 借助水流解决问题的网络流 3.5.1 最大流 3.5.2 最小割 ...
数据结构:一般堆、二项堆、斐波那契堆、红黑树、通用散列(采用全域散列和完全散列技术)、不相交集合、任意维数组、高维对称数组。 图论算法(兼容有向图,无向图):广度和深度优先遍历、确定图是否存在回路、...
数据结构:一般堆、二项堆、斐波那契堆、红黑树、通用散列(采用全域散列和完全散列技术)、不相交集合、任意维数组、高维对称数组。 图论算法(兼容有向图,无向图):广度和深度优先遍历、确定图是否存在回路、...
acm常用代码及算法,对我的帮助很大 1.精度计算——大数阶乘 2.精度计算——乘法(大数乘小数...数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树 一、数学问题 1.精度计算——大数
数学问题: 1.精度计算——大数阶 乘 2.精度计算——乘法 (大数乘小数) 3.精度计算——乘法 (大数乘大数) 4.精度计算——加法 5.精度计算——减法 6....数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树
leetcode新手刷题指南 Leetcode 刷题指南 参考中的刷题顺序链接到 leetcode 官网中,方便直接跳转到刷题页面。...高级数据结构经典题目 并查集 最小生成树 线段树 树状数组 字典树 海量数据处理 算法模板
图论之所以运用最多是因为它的变化最多,而且可以轻易地结合基本数据结构和许多算法的基本思想,较多用到的知识包括连通性判断、DFS和BFS,关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流...
OpenSAL1.1 包含了算法导论中所有数据结构和算法以及其他内容,本资源为该算法库的静态链接库 内容如下(*号表示1.1版本新增内容): 数据结构:一般堆、二项堆、斐波那契堆、红黑树、通用散列(采用全域散列和完全...
数组、栈、队列、链表、二分搜索树、集合、映射、优先队列、堆、线段树、Trie、并查集、AVL、红黑树、哈希表 数据处理典型案例,逐渐更新 :hot_beverage: Java 、、基本概念、面向对象、基本数据类型与运算、字符串...
2.2 简单数据的存储——preferences 33 2.2.1 preferences简介 33 2.2.2 preferences实现访问时间的记录 33 2.3 手机自带数据库——sqlite 34 2.3.1 初识sqlite 35 2.3.2 sqlite数据库的基本操作 ...
2个目标文件,FTP的目标是:(1)提高文件的共享性(计算机程序和/或数据),(2)鼓励间接地(通过程序)使用远程计算机,(3)保护用户因主机之间的文件存储系统导致的变化,(4)为了可靠和高效地传输,虽然用户...