首页 > 其他分享 >二维数点总结

二维数点总结

时间:2024-11-11 11:43:00浏览次数:1  
标签:总结 前缀 询问 数点 差分 二维 扫描线 DS

有很多数数题都可以转化为二维数点模型。将一些二元信息视作平面上的若干个点,查询即数一个矩形中有多少个点/点的权值之和等信息。

那么这很明显是DS题(或者至少要上DS优化一下)。我们来想想怎么处理矩阵查询。

离线

离线的时候做法很多。

但基本都有一个共性:把询问差分,转化为前缀信息(在平面上反映出来的是以原点为一个顶点的矩形的信息)。

BIT/线段树

我们把询问差分之后,再按\(x\)排序,然后就可以运用扫描线的思想。

我们将询问同样视作一个点(即以原点为一个顶点的矩形的不在坐标轴上的那个顶点)。将维护的DS视作一条竖直的扫描线,从左至右扫(从右至左也可以,只是差分方式和一些细节改一下,具体选择看数点部分以外的东西怎样方便实现)。

将扫到的点都加入DS中,再来处理扫描线扫到的询问。我们发现扫描线使得一个平面上的前缀信息在扫描线上对应着序列的前缀,于是直接查询DS的前缀信息即可回答询问。

写的时候注意常数问题,并且数清楚复杂度有几只\(\log\)。

CDQ分治

不太会写,口胡一下。

同样差分询问,然后发现就是数\((x,y)\)左下方有多少个点。这是一个二维偏序,于是CDQ就好了。

在线

使用一些高级数据结构就可以在线了。

树套树

显然是可以数清楚有多少个点的,就是难写,而且似乎比离线BIT多一只\(\log\)。

KDT

这位更是重量级,但是我不会。

术业有专攻,KDT就是干这个的。

标签:总结,前缀,询问,数点,差分,二维,扫描线,DS
From: https://www.cnblogs.com/EmilyDavid/p/18538993

相关文章

  • Linux 查找命令总结
    在使用linux时,经常需要进行文件查找。五种命令是有区别的。区别:(1)find 根据文件的属性进行查找,如文件名,文件大小,所有者,所属组,是否为空,访问时间,修改时间等。(2)grep根据文件的内容进行查找,会对文件的每一行按照给定的模式(patter)进行匹配查找。(3)which 查看可执行文件......
  • # 学期(2024-2025-1) 学号(20241420) 《计算机基础与程序设计》第七周学习总结
    学期(2024-2025-1)学号(20241420)《计算机基础与程序设计》第七周学习总结作业信息这个作业属于哪个课程<班级链接>(如2024-2025-1-计算机基础与程序设计)这个作业要求在哪里<作业要求链接>(2024-2025-1计算机基础与程序设计第七周作业)这个作业的目标<计算机科学概论......
  • 2024-2025-1 20241425 《计算机基础与程序设计》第7周学习总结
    2024-2025-120241425《计算机基础与程序设计》第7周学习总结作业信息这个作业属于哪个课程[2024-2025-1-计算机基础与程序设计](https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP)这个作业要求在哪里<作业要求的链接>(如2024-2025-1计算机基础与程序设计第一......
  • 2024-2025-1 学号20241306 《计算机基础与程序设计》第7周学习总结
    2024-2025-1学号20241306《计算机基础与程序设计》第7周学习总结作业信息这个作业属于哪个课程<班级的链接>2024-2025-1-计算机基础与程序设计这个作业要求在哪里<作业要求的链接>(如2024-2025-1计算机基础与程序设计第一周作业)这个作业的目标了解学习数组与链......
  • 2024-2025-1 20241406刘书含《计算机基础与程序设计》第七周学习总结
    作业信息作业课程 2024-2025-1-计算机基础与程序设计作业要求 2024-2025-1计算机基础与程序设计第七周作业作业目标 数组与链表,基于数组和基于链表实现数据结构,无序表与有序表,树,图,子程序与参数作业正文 2024-2025-120241328《计算机基础与程序设计》第七周学习总结教材学习......
  • 11.4-11.10做题总结
    自从CCF出分,到得知自己考了150pts,再到得知自己无法参加NOIP,我的内心一直是悲痛的。WB老师之后让我做LYD做的算法进阶指南。tx告诉我acwing上有单独题单,于是一直做acwing的题。AcWing89.a^b快速幂即可。AcWing5579.增加模数拆开。AcWing90.64位整数乘法......
  • 2024-2025-1 20241408陈烨南《计算机基础与程序设计》第七周学习总结
    这个作业属于哪个课程2024-2025-1-计算机基础与程序设计)这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK07这个作业的目标数组与链表、基于数组和基于链表实现数据结构、无序表与有序表、树、图、子程序与参数作业正文本博客链接教......
  • 2024-2025-1 20241328 《计算机基础与程序设计》第七周学习总结
    2024-2025-120241328《计算机基础与程序设计》第七周学习总结作业信息作业课程2024-2025-1-计算机基础与程序设计作业要求2024-2025-1计算机基础与程序设计第七周作业作业目标数组与链表,基于数组和基于链表实现数据结构,无序表与有序表,树,图,子程序与参数作业正......
  • # 学期2024-2025-1 学号20241416《计算机基础与程序设计》第7周学习总结
    这个作业属于哪个课程 https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP/这个作业要求在哪里 https://www.cnblogs.com/rocedu/p/9577842.html#WEEK07这个作业的目标 数组与链表、基于数组和基于链表实现数据结构、无序表作业正文 https://www.cnblogs.com/rockytyh/p/1......
  • 2024-2025-1 20241421 《计算机基础与程序设计》第七周学习总结
    作业信息这个作业属于哪个课程 2024-2025-1-计算机基础与程序设计这个作业要求在哪里 2024-2025-1计算机基础与程序设计第七周作业这个作业的目标 数组与链表、基于数组和基于链表实现数据结构、无序表与有序表、树、图、子程序与参数作业正文 https://www.cnblogs.com/118qa......