【hdu1255】线段树求矩形面积交
2024-08-29 18:29:34
题意大概就是上图这个样子。<=100组测试数据,每组<=1000个矩形。
题解:
这个问题怎么解决。。做了上一题矩形面积并应该就会了。。
对于每个节点维护3个值:
cnt:该节点所代表的这条线段被覆盖了多少次
len1:该节点所管理区间中被覆盖了>=1次的线段总长
len2:该节点所管理区间中被覆盖了>=2次的线段总长
为什么要维护两个呢?因为要是只维护len2,那子树中要是有个覆盖了一次的,然后该节点覆盖一次,那么怎么更新len2丫。。
怎么更新?
void upd(int x)
{
int lc=t[x].lc,rc=t[x].rc;
if(t[x].cnt>=) //如果该点被覆盖了两次
t[x].len1=t[x].len2=t[x].rl;//len1和len2=该节点所代表线段的长度
if(t[x].cnt==)//如果该点只被覆盖了一次
{
t[x].len1=t[x].rl;//len1=全长
t[x].len2=t[lc].len1+t[rc].len1;//孩子中有些只被覆盖了一次的变成覆盖了两次
}
if(t[x].cnt==)//如果没被覆盖,那就直接上传更新。
{
t[x].len1=t[lc].len1+t[rc].len1;
t[x].len2=t[lc].len2+t[rc].len2;
}
}
一开始我在纠结一种情况:一个节点现在被覆盖一次,它的子树中原本有个节点被覆盖了一次,那么怎么更新?维护一个从根节点往下的sum值吗?
后来我发现该节点的len2可以直接用孩子的len1更新就好。
弱弱弱弱弱弱弱弱弱弱弱弱弱弱弱弱
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std; const int N=,INF=(int)1e9;
double z[N][];
struct point{
double d;
int x,y;
}p[*N];
struct node{
int x0,x1,d;
double y;
}a[N];
struct trnode{
int l,r,lc,rc,cnt,lazy;
double rl,len1,len2;
//len1以x为根的子树中表示被覆盖了>=1次的线段长度,len2表示以x为根的子树中被覆盖了>=2次的线段的长度
}t[*N];
double num[N];
int n,tl,pl,al; int minn(int x,int y){return x<y ? x:y;}
int maxx(int x,int y){return x>y ? x:y;}
bool cmp_d(point x,point y){return x.d<y.d;}
bool cmp_y(node x,node y){return x.y<y.y;} int bt(int l,int r)
{
int x=++tl;
t[x].l=l;t[x].r=r;
t[x].lc=t[x].rc=;
t[x].cnt=;t[x].lazy=;
t[x].len1=t[x].len2=;
t[x].rl=num[r+]-num[l];
if(l<r)
{
int mid=(l+r)/;
t[x].lc=bt(l,mid);
t[x].rc=bt(mid+,r);
}
return x;
} void upd(int x)
{
int lc=t[x].lc,rc=t[x].rc;
if(t[x].cnt>=) //如果该点被覆盖了两次
t[x].len1=t[x].len2=t[x].rl;//len1和len2=该节点所代表线段的长度
if(t[x].cnt==)//如果该点只被覆盖了一次
{
t[x].len1=t[x].rl;//len1=全长
t[x].len2=t[lc].len1+t[rc].len1;//孩子中有些只被覆盖了一次的变成覆盖了两次
}
if(t[x].cnt==)//如果没被覆盖,那就直接上传更新。
{
t[x].len1=t[lc].len1+t[rc].len1;
t[x].len2=t[lc].len2+t[rc].len2;
}
} void change(int x,int l,int r,int d,int sum)
{
if(t[x].l==l && t[x].r==r)
{
t[x].cnt+=d;
upd(x);
return ;
}
int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)/;
if(r<=mid) change(lc,l,r,d,sum+t[x].cnt);
else if(l>mid) change(rc,l,r,d,sum+t[x].cnt);
else
{
change(lc,l,mid,d,sum+t[x].cnt);
change(rc,mid+,r,d,sum+t[x].cnt);
}
upd(x);
} void output()
{
for(int i=;i<=tl;i++)
printf("l = %d r = %d cnt = %d len1 = %lf len2 = %lf rl = %lf \n",t[i].l,t[i].r,t[i].cnt,t[i].len1,t[i].len2,t[i].rl);
} int main()
{
freopen("a.in","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
if(n==) break;
int x,mx;pl=;tl=;al=;t[].len1=t[].len2=;
for(int i=;i<=n;i++)
{
for(int j=;j<=;j++)
{
scanf("%lf",&z[i][j]);
if(j%==) p[++pl].d=z[i][j],p[pl].x=i,p[pl].y=j;
}
}
sort(p+,p++pl,cmp_d);
mx=;p[].d=INF;
for(int i=;i<=pl;i++)
{
if(p[i].d!=p[i-].d) mx++,num[mx]=p[i].d;
z[p[i].x][p[i].y]=mx;
}
bt(,mx-);//debug n个节点只有n-1条线段
for(int i=;i<=n;i++)
{
if(z[i][]<z[i][]) swap(z[i][],z[i][]);
if(z[i][]>z[i][]) swap(z[i][],z[i][]);
a[++al].x0=z[i][];a[al].x1=z[i][];a[al].y=z[i][];a[al].d=-;
a[++al].x0=z[i][];a[al].x1=z[i][];a[al].y=z[i][];a[al].d=;
}
sort(a+,a++al,cmp_y);
double w,h,ans=;
change(,a[].x0,a[].x1-,a[].d,);
for(int i=;i<=al;i++)
{
h=a[i].y-a[i-].y;
w=t[].len2;
ans+=w*h;
change(,a[i].x0,a[i].x1-,a[i].d,);
}
printf("%.2lf\n",ans);
}
return ;
}
最新文章
- HTML5 兼容IE浏览器
- [JAVA] java class 基本定义 Note
- [转]as3 算法实例【输出1 到最大的N 位数 题目:输入数字n,按顺序输出从1 最大的n 位10 进制数。比如输入3,则输出1、2、3 一直到最大的3 位数即999。】
- MATLAB for循环优化三例
- spring mvc4.1.6 + spring4.1.6 + hibernate4.3.11 + mysql5.5.25 开发环境搭建及相关说明
- Winform项目调用asp.net数据接口
- Go语言并发与并行学习笔记(三)
- ACID CAP BASE介绍
- PyCharm 4.0下载(附keygen)
- poj1716 Integer Intervals(差分约束)
- SQL语言类
- LoadRunner11_录制Oracle数据库脚本
- PE文件格式详解,第一讲,DOS头文件格式
- TensorFlow文档翻译-01-TensorFlow入门
- MySQL主从复制的配置
- 虚拟环境更新HA
- 转发 ---->; 2018年阿里巴巴重要开源项目汇总(持续更新中)
- 从session原理出发解决微信小程序的登陆问题
- Ngon 是啥
- django学习之命令
热门文章
- 安装配置erlang_db_driver
- 浅谈 Vue v-model指令的实现原理 - 如何利用v-model设计自定义的表单组件
- java出现以下警告:WARN No appenders;WARN Please initialize the log4j的处理方法
- 【Linux】- 开启远程连接
- WPF绑定到父元素的属性的方法
- springBoot @EnableAutoConfiguration深入分析
- bzoj3782上学路线
- OpenStack Queens版本Horizon定制化开发
- Tensorflow框架初尝试————搭建卷积神经网络做MNIST问题
- C#基础-连接Access与SQL Server