首页 > 其他分享 >南外集训 2024.1.8 T3

南外集训 2024.1.8 T3

时间:2024-01-08 20:55:19浏览次数:40  
标签:2024.1 le 前缀 最大值 位置 T3 南外 序列 考虑

题意

给定一个序列 \(a\),将之划分为两个子序列,使得两个序列前缀最大值的和之和最小。

\(1\le n\le 5\times 10^5, 1\le a_i\le 10^9\)

做法

首先 DP 很容易做到平方:考虑前 \(i\) 个数,其中一个子序列当前的最大值当然是前 \(i\) 个数的最大值,记另一个序列的最大值是 \(j\),此时的最小代价记为 \(f_{i,j}\)。

考虑这个 DP 的转移:对于当前数 \(a_i\) 如果它是前缀最大值,那么显然是给所有位置加 \(a_i\);如果不是,则 \(f_{i,a_i}\) 变为所有 \(j\le i\) 的 \(f_{i-1,j}\) 的最小值再加上 \(a_i\),小于 \(i\) 的位置加上当前前缀最大值,大于 \(i\) 的位置加上那个位置的数值。这个过程显然可以用 Kinetic Tournament Tree 维护,时间复杂度有人证明是 \(\mathrm O(n\log^2 n)\),可以通过。

下面是官方题解:考虑用 set 维护一个单调栈,在整个过程中,如果前面的某个位置小于等于后面的某个位置,则把后面的位置删除。对于 \(a_i\) 是前缀最大值的情况当然好处理,考虑不是。大于 \(i\) 的位置的部分考虑用一个线段树维护每个位置再被加多少次会比下一个位置大,那么每次只要处理一下边界,然后用线段树定位要删除的点即可。前半部分的区间加可能会导致后面的某些位置重新进入单调栈,但是由于 \(a_i\) 这个位置被赋值为前面的最小值,所以在它后面的位置无法重新进入到单调栈中,所以只需要考虑 \(a_i\) 即可。时间复杂度 \(\Theta(n\log n)\)。

标签:2024.1,le,前缀,最大值,位置,T3,南外,序列,考虑
From: https://www.cnblogs.com/kyeecccccc/p/17953201

相关文章

  • 2024.1.6做题纪要
    P4390[BalkanOI2007]Mokia摩基亚/(离线)简单题第一眼看题,emmm,跟分治有半毛钱关系啊!!!!这每次分治一次不直接复杂度爆炸??冷静下来后,我们发现对于一个点,对于区间产生贡献充要条件是他的\(x\)轴要在区间内。所以。。。我们是不是可以离线下来对于\(x\)轴排一遍序,我们只有左半部......
  • 2024.1.6做题总结
    luogu2258[NOIP2014普及组]子矩阵本题乍一看数据范围很小,但是如果暴力的话时间复杂度为\(O(C^r_nC^c_m)\),在最坏情况(\(r=\frac{1}{2}n,c=\frac{1}{2}m\))下过不了。本题满足最优化,但是没得贪,二维好像不好跑dp啊。可以枚举哪些行,然后跑一维的dp。我们用一个dfs固定一下......
  • Solution Set【2024.1.5】
    明天再补。[POI2011]LightningConductor设\(f_i\)表示只考虑\(\left[1,i\right]\)的情况下\(i\)的答案,那么有:\[f_i=\max\limits_{j\lei}a_j-a_i+\sqrt{\left\lverti-j\right\rvert}\]发现其满足四边形不等式,于是使用分治优化即可。时间复杂度\(O(n\log......
  • 2024.1.5——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.ERP明日计划:学习......
  • 南外集训 2024.1.5 T3
    非常简单的一道题。要好好反思为什么没有做出来。题意给定一棵点带权的树,强制在线询问一条链上取恰好\(m\)个数按位与的最大值。\(1\len\le10^6,1\leq\le10^5,1\lem\le10,0\leV<2^{62}\)。解法考虑一个暴力:取出树链上所有点权,二分答案\(x\),则需要检查是否存在至......
  • MMBT3904资料手册参数解读及应用示例分享
    MMBT3904是一种三极小信号NPN晶体管。它具有低噪声、高放大倍数和较高的开关速度等特点。MMBT3904广泛应用于放大、开关和驱动电路等领域。它是一款常见的通用型晶体管,常被用于低功耗设备和数字电路中。常用于低电压、中电流放大应用。MMBT3904重要参数解读最大集电极电流(ICmax):这是......
  • MMBT3906-ASEMI低压PNP型贴片三极管MMBT3906
    编辑:llMMBT3906-ASEMI低压PNP型贴片三极管MMBT3906型号:MMBT3906品牌:ASEMI电流(Id):200mA电压(Vdss):40V功率(Pd):芯片个数:1封装:SOT-23安装方式:表面安装工作温度:-55°C~150°C引脚数量:3类型:低压低电流PNP型晶体管MMBT3906描述:MMBT3906是一颗通用PNP型晶体管,它的特点是电压连续可调,低动......
  • MMBT3904-ASEMI智能灯具三极管MMBT3904
    编辑:llMMBT3904-ASEMI智能灯具三极管MMBT3904型号:MMBT3904品牌:ASEMI封装:SOT-23集电极电流(Id):200mA发射极击穿电压(Vdss):40V芯片个数:1引脚数量:3类型:MOS管特性:NPN低电流晶体三极管封装尺寸:如图集电极-基极击穿电压:60V工作温度:-55°C~150°CMMBT3904特性:用于通用放大器和开关。开关......
  • 初识Sringboot3+vue3环境准备
    环境准备后端环境准备下载JDK17https://www.oracle.com/java/technologies/downloads/#jdk17-windows   安装就下一步下一步,选择安装路径 配置环境 环境JDK17+、IDEA2021+、maven3.5+、vscode后端基础:javaSE,javaWeb、JDBC、SMM框架(Spring+SpringMVC+MyBatis)、MyBatis-Plus前......
  • 2024.1.1 Java学习
    1.前缀自增自减法:先进行自增或自减运算,在进行表达式运算2.后缀自增自减法:先进行表达式运算,再进行自增或自减运算3.位运算符,作用在所有的位上。&:如果相对应位都是1,结果为1|:相对应位有1位是1,结果为1^:相对应位不同,结果为1~:按位取反,0变1,1变0<<:左操作数按位左移右操作数指定......