首页 > 其他分享 >P5386 [Cnoi2019] 数字游戏

P5386 [Cnoi2019] 数字游戏

时间:2024-03-01 21:33:28浏览次数:33  
标签:游戏 text 复杂度 Cnoi2019 sqrt len 端点 P5386 mathcal

我永远喜欢数据结构。

题目传送门

  • 给出长度为 \(n\) 的排列 \(a_1\sim a_n\),\(m\) 次询问有多少对 \([l,r]\) 满足 \(L\le l\le r\le R\) 且 \(\forall \,i\in [L,R],a_i\in[X,Y]\)。

  • \(n,m\le 2\times 10^5\)。

  • \(\text{3 s}\sim\text{7 s / 125 MB}\)。

下文中默认 \(\mathcal{O}(n)=\mathcal{O}(m)\),分块以 \(\mathcal{O}(\sqrt{n})\) 为块长。

考虑对 \([X,Y]\) 这个限制莫队。设当前维护的值域区间是 \([x,y]\),令 \(w_i=[x\le a_i\le y]\)。对于一个询问我们要求当 \(x,y\) 分别扫到 \(X,Y\) 时,\(w\) 数组的区间 \([L,R]\) 内有多少全部为 \(1\) 的子区间。

由于给出的是一个排列,\(x,y\) 移动一步时只会带来 \(b\) 数组一个位置的改变。相当于要支持单点 \(0\) 变 \(1\)(或 \(1\) 变 \(0\)),区间查询 \([L,R]\) 内有多少全部为 \(1\) 的子区间(简称为答案)。

考虑线段树,一个节点维护一下几个信息:

  • \(\text{len}\):代表这个节点对应的区间长度。

  • \(\text{llen}\):代表这个节点对应的区间中,以左端点开始的最长连续 \(1\) 段长度。

  • \(\text{rlen}\):代表这个节点对应的区间中,以右端点结束的最长连续 \(1\) 段长度。

  • \(\text{sum}\):代表这个节点对应的区间的答案。

合并两个节点 \(u,v\) 的信息时,都考虑该信息是否跨过中点。具体地,设 \(\otimes\) 为合并操作:

  • \(\text{len}_{u\otimes v}=\text{len}_u+\text{len}_v\)

  • \(\text{llen}_{u\otimes v}=\begin{cases}\text{len}_u+\text{llen}_v,\text{len}_u=\text{llen}_u\\\text{llen}_u,\text{otherwise}\end{cases}\)

  • \(\text{rlen}_{u\otimes v}=\begin{cases}\text{len}_v+\text{rlen}_u,\text{len}_v=\text{rlen}_v\\\text{rlen}_v,\text{otherwise}\end{cases}\)

  • \(\text{sum}_{u\otimes v}=\text{sum}_u+\text{sum}_v+\text{rlen}_u\cdot\text{llen}_v\)

容易支持单点修改。这样做时间复杂度为 \(\mathcal{O}(n\sqrt{n}\log n)\),空间复杂度为 \(\mathcal{O}(n)\)。不够优美。

原因是修改数量为 \(\mathcal{O}(n\sqrt{n})\),而询问数量仅有 \(\mathcal{O}(n)\)。考虑换成 \(\mathcal{O}(1)\) 修改 \(\mathcal{O}(\sqrt{n})\) 查询的分块。

记:

  • \(\text{bl}_i,\text{br}_i\) 为第 \(i\) 块的左右端点。

  • \(\text{bel}_i\) 为 \(i\) 位置所在块。

  • \(A_i\) 为第 \(i\) 块的信息。

  • \(\text{pos}_i\) 的意义如下:若 \(i\) 是这个块中一个极长 \(1\) 连续段的端点,则 \(\text{pos}_i\) 的值为它所在极长 \(1\) 连续段的另一个端点;否则 \(\text{pos}_i=0\)。

考虑 \(w_i\) 由 \(0\) 变 \(1\) 怎么修改。考虑修改后极长 \(1\) 连续段的情况怎么变,显然它只可能接上修改前 \(i-1\) 所在极长 \(1\) 连续段和 \(i+1\) 所在极长 \(1\) 连续段。以此来处理 \(\text{pos}\) 数组的变化。注意不存在这两个位置或这两个位置与 \(i\) 不在同一块中的情况,具体可以看代码,个人认为讨论了所有可能的情况,虽然有一些繁杂。

处理好修改后 \(i\) 所在极长 \(1\) 连续段后,新增的答案就是这个段中包含 \(i\) 的子区间数量,是容易计算的。

至于 \(\text{llen}\) 和 \(\text{rlen}\) 的变化,容易通过修改后的 \(\text{pos}\) 数组求出。

但是发现 \(w_i\) 由 \(1\) 变 \(0\) 的情况不好处理,于是考虑回滚莫队,每次撤销最新的一次 \(0\) 变 \(1\) 回退上一个版本。用栈按时间顺序存储修改的量即可。

查询可以考虑从左往右遍历每个查询区间中的块(包括散块),散块暴力计算信息,整块就用维护好的 \(A_i\),然后像上面那样合并。

处理询问时,对于左右端点在莫队中分出的块相同时,对于 \([X,Y]\) 这个值域,让指针 \(j\) 从 \(X\) 扫到 \(Y\) 暴力更新 \([X,j]\) 的信息。然后查询、撤销。单次时间复杂度为 \(\mathcal{O}(\sqrt{n})\)。

剩下的询问离线跑回滚莫队。每次做一段左端点在莫队中分出的块相同的询问。假设这一块的右端点为 \(R_0\),我们只考虑撤销 \([X,R_0]\) 的操作,保留 \((R_0,Y]\) 的操作。这样对于排序后的每一个询问 \(i\),可以先从上一个询问的 \((R_0,Y_{i-1}]\) 扩展到这个询问的 \((R_0,Y_i]\),再添加 \([X,R_0]\) 的操作,再查询,再撤销这些操作回到 \((R_0,Y_i]\) 的版本,再继续做下一个询问。

做完一段左端点所在块相同的询问后,暴力清空分块。由于只会有 \(\mathcal{O}(\sqrt{n})\) 种左端点所在块,即这么多次清空,所以清空的总时间复杂度是 \(\mathcal{O}(n\sqrt{n})\)。

修改的和查询的总复杂度都是 \(\mathcal{O}(n\sqrt{n})\)。因此,回滚莫队的做法时间复杂度为 \(\mathcal{O}(n\sqrt{n})\),空间复杂度为 \(\mathcal{O}(n)\)。可以接受。

AC Link

AC Code

标签:游戏,text,复杂度,Cnoi2019,sqrt,len,端点,P5386,mathcal
From: https://www.cnblogs.com/MnZnOIerLzy/p/18047996

相关文章

  • 代码随想录算法训练营第三十二天 | 45.跳跃游戏II ,55. 跳跃游戏,122.买卖股票的最佳时
     122.买卖股票的最佳时机II 已解答中等 相关标签相关企业 给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购......
  • 9-3. 打包生成游戏
    打包前需要一个初始场景新建一个场景,名叫Initialization,然后在它下面挂载一个GameObject名叫InitialLoad,上面挂载一个脚本InitialLoad,内容为usingSystem.Collections;usingSystem.Collections.Generic;usingUnityEngine;usingUnityEngine.AddressableAssets;publicc......
  • (32/60)买卖股票的最佳时机Ⅱ、跳跃游戏、跳跃游戏Ⅱ
    想不到,根本想不到买卖股票的最佳时机Ⅱleetcode:122.买卖股票的最佳时机II贪心法思路任何一天的累计利润都可以拆成之前每天相比前一天的利润之和,因此最大利润就是收集了每天的正利润。复杂度分析时间复杂度:O(N)。空间复杂度:O(1)。注意点略代码实现classSolution......
  • <教程> 我的游戏专用头文件 —— game.h
    这是一篇自制头文件的教程目录一、自制头文件其实自制头文件就和打代码一样,写下你自己的函数或者引用另外的头文件当然,不要在头文件里写\(main\)函数!创建头文件很简单,使用*.h的文件名即可(如game.h)编写头文件一般要包括下面的代码#ifndefSDGS//判断是否#define......
  • P3706 「SDOI2017」硬币游戏 解题报告
    oj:https://gxyzoj.com/d/hzoj/p/P451概率与期望+hash+高斯消元声明一些东西,pre(S,l)表示串S的长度为l的前缀,lst(S,l)表示串S的长度为l的后缀一.对于所有串建立字典树,像「HNOI2013」游走一样高斯消元,时间复杂度\(O(n^3m^3)\),预计50/70pts二.正解:显然,n项中,出现一个长度......
  • 洛谷题单指南-贪心-P1080 [NOIP2012 提高组] 国王游戏
    原题链接:https://www.luogu.com.cn/problem/P1080题意解读:通过不同的排队方式,让获得最多奖赏的大臣金额尽可能的少。此题如果没有思路,用全排列枚举可以“骗”分,更好的做法直觉上是某种贪心策略,另外基于数据规模考虑,要拿满分,需要上高精度。下面就由浅入深一步一步的解决。解题思......
  • 基于Rust的Tile-Based游戏开发杂记(01)导入
    什么是Tile-Based游戏?Tile-based游戏是一种使用tile(译为:瓦片,瓷砖)作为基本构建单位来设计游戏关卡、地图或其他视觉元素的游戏类型。在这样的游戏中,游戏世界的背景、地形、环境等都是由一系列预先定义好的小图片(即tiles)拼接而成的网格状结构。每个tile通常代表一个固定的尺寸区域,......
  • 最新Unity游戏主程进阶学习大纲(2个月)
    过完年了,很多同学开始重新规划自己的职业方向,找更好的机会,准备升职或加薪。今天给那些工作了1~5年的开发者梳理”游戏开发客户端主程”的学习大纲,帮助大家做好面试准备。适合Unity客户端开发者。进阶主程其实就是从固定的几个方面搭建好完整的知识体系做好对应的回答和准备,学习......
  • Unity对象池(应用:游戏音效管理系统)
    打算为项目增加音效,但是没有头绪不知从何做起。想要做一个便于拓展的音效管理系统,通过搜集网上资料暂时得到以下两种方案。(虽然实现方式远不止两种)其中对象池技术早有耳闻,趁此机会学习并应用。一、创建一个AudioManagerAudioManager通常是一个单例(Singleton)类,负责管理和播放游戏......
  • 酷睿Ultra 7游戏实测:不比入门独显差
    新一代酷睿Ultra采用了全新的设计,与以往英特尔处理器完全不同。从性能的角度来看,处理器部分的变化并不是特别大,不过核芯显卡的性能提升非常巨大,甚至相比上一代直接翻倍,与入门级独显都有一战之力。那么,酷睿Ultra的核芯显卡性能到底有多强,在实际游戏中会有什么样的表现,下面我们就通......