首页 > 其他分享 >扫描线

扫描线

时间:2022-09-04 18:00:13浏览次数:58  
标签:单点 留存 扫描线 操作 维护 数据结构

1离线

2支持单点查询

3单点维护操作顺序及其他信息 从而维护历史信息(数据结构基于操作这一维)

4对操作进行差分 扫描时扫到改点时留存的操作就是位于该点的操作

5可对数据结构进行二分等一系列操作达到奇怪的目的

6相比树套树 每次只维护单个位置 所以每次只用留存一维空间 从而也不支持在线

 

标签:单点,留存,扫描线,操作,维护,数据结构
From: https://www.cnblogs.com/Sakura-Lu/p/16655598.html

相关文章

  • 扫描线
    扫描线的一些经典应用:求n个矩形的面积并和周长并。面积并(P5490【模板】扫描线)首先扫描线的思想就是假设有一条无限长度的线从一个方向到另一个方向扫一遍整个图形,这样......
  • 模拟赛 d (扫描线,三维偏序,线段树合并,并查集,线段树上二分)
    PRO题目大意:给定$N$个矩形,求连通块个数。($1\leqN,x_1,x_2,y-1,y_2\leq100000$)SOL乍一看就能知道是扫描线,不过这题的细节恐怖的要命。(std同样看不懂,自己魔改了一......
  • 【学习笔记/模板】扫描线 周长并
    先开坑,晚上再写。P1856[IOI1998][USACO5.5]矩形周长PictureCode#include<cstdio>#include<algorithm>usingnamespacestd;constintMAXN=1e5+10;intn,......
  • acwing 1228. 油漆面积 扫描线
     X星球的一批考古机器人正在一片废墟上考古。该区域的地面坚硬如石、平整如镜。管理人员为方便,建立了标准的直角坐标系。每个机器人都各有特长、身怀绝技。它们感兴......