首页 > 其他分享 >2023.12.25 近期练习

2023.12.25 近期练习

时间:2023-12-25 21:11:59浏览次数:37  
标签:25 frac log 2023.12 练习 sqrt 扫描线 维护

CF1793F

有一个朴素的想法,使用不删除莫队,使用一种数据结构维护相邻元素的差,\(O(n\sqrt q \log n)\)。
可以通过链表加不增加莫队,维护最小值,使用值域分块,\(O(n\sqrt q+q\sqrt n)\)。
即使如此,也因为常数过大无法通过。
考虑使用扫描线,从右往左扫描区间,将询问挂到左端点上。
大于小于是等价的,先处理大于的。
我们假设现在扫到 \(a_i\),同步记录一个 \(f_j\) 表示 \([i,j]\) 的答案。
先找到右边第一个大于 \(a_i\) 的,设为 \(a_j\),并将 \(j\) 点更新为 \(a_j-a_i\)。
下一步,找下一个 \(a_k\in [a_i,a_j)\),并继续地更新。
这里有一个优化,就是 \(a_k\) 的范围可以调整为 \([a_i,\frac{a_i+a_j}{2}]\),因为在 \([\frac{a_i+a_j}{2},a_j]\) 的势必与 \(a_j\) 更近。
每次范围都减半,保证了复杂度,为 \(O(n\log ^2n +q\log n)\)。
具体地,开一棵值域线段树维护当前值最小的位置,再开一棵线段树维护区间 \(f\) 的值。
这种问题是经典的区间询问问题,允许离线的话,应使用经典的扫描线模型。

标签:25,frac,log,2023.12,练习,sqrt,扫描线,维护
From: https://www.cnblogs.com/Simon-Gao/p/17926987.html

相关文章

  • 闲话12.25
    我草今天累死了......
  • P1259 黑白棋子的移动(函数预处理)
    P1259黑白棋子的移动个人感想终于不用看题解的思路写题了(大概率是题比较简单)函数预处理如果要实现两个函数间的互相调用,直接使用会报错,因为在你第一个函数中调用的第二个函数其实还没被定义。所以需要进行函数的预处理,将次函数(排序较后的函数)可以预处理定义即可解决。解题思......
  • 12.25每日总结3
    晚上做了大数据实验6实验6熟悉Hive的基本操作 1.实验目的(1)理解Hive作为数据仓库在Hadoop体系结构中的角色。(2)熟练使用常用的HiveQL。2.实验平台操作系统:Ubuntu18.04(或Ubuntu16.04)。Hadoop版本:3.1.3。Hive版本:3.1.2。JDK版本:1.8。3.数据集由《Hive编程指南》(O'Reill......
  • 云原生周刊:Karmada 成为 CNCF 孵化项目 | 2023.12.25
    开源项目推荐kubernetes-reflectorReflector是一个Kubernetes的插件,旨在监视资源(secrets和configmaps)的变化,并将这些变化反映到同一命名空间或其他命名空间中的镜像资源中。LingoLingo是适用于K8s的OpenAI兼容LLM代理和自动缩放器。canary-checkercanary-checke......
  • 天池AI练习生计划 - 第三期数据分析入门与实践,火热进行中!通关赢取双重礼品!
    《Numpy实践》《Pandas实践》课程带您了解numpy与pandas的所有核心操作与特性;《Matplotlib实践》课程助您解决用python做数据可视化时面临的两大痛点。轻松来闯关,即可领取双重礼品~实训培训证书:通关两个关卡即可领取家用纯棉毛巾:通关全部关卡即可领取活动地址:https://tianchi.......
  • 12.25每日总结2
    今天中午接着做大数据的实验实验8Flink初级编程实践 1.实验目的(1)通过实验掌握基本的Flink编程方法。(2)掌握用IntelliJIDEA工具编写Flink程序的方法。2.实验平台(1)Ubuntu18.04(或Ubuntu16.04)。(2)IntelliJIDEA。(3)Flink1.9.1。3.实验步骤(1)使用IntelliJIDEA工具开发WordCo......
  • 12月25日打卡
    今天完成优化了一下软件构造的实验一的相关内容。完成百度翻译GUI相关功能代码并测试调用,要求可以实现中文翻译成英文,英文翻译成中文Sample.javaimportorg.json.JSONException;importorg.json.JSONObject;importjava.io.*;importjava.net.HttpURLConnection;importj......
  • Windows Server 2025 简体中文版下载 (Inside Preview, updated Dec 2023) - 下一代 W
    WindowsServer2025简体中文版下载(InsidePreview,updatedDec2023)-下一代Windows11ServerWindowsServerNext请访问原文链接:https://sysin.org/blog/windows-server-2025/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org我们知道WindowsServer2022......
  • 12/25每日总结
    树与二叉树的转化树要变成二叉树,那就将树中的所有兄弟结点进行链接,然后每一层与上一层的连接只留下第一个结点的连接二叉树要变成树,那就反方向来一次,将除了第一个结点的其他结点与根节点连接上,然后将兄弟结点连接,这时候二叉树就变回了原来的树森林与二叉树的转化森林转化为二叉树,森......
  • 每日总结2023年12月25日
    临近期末,最近事比较多,对之前软件构造实验做一个汇总软件构造实验作业实验名称:百度机器翻译SDK实验,百度图像增强与特效SDK实验,JFinal极速开发框架实验班级:信2105-1 学号:20214309 姓名:陈俊杰 实验一:百度机器翻译SDK实验一、实验要求任务一:下载配置百度翻译Java相关库及......