首页 > 其他分享 >P3242 [HNOI2015] 接水果 抽象做法

P3242 [HNOI2015] 接水果 抽象做法

时间:2024-03-16 16:23:30浏览次数:28  
标签:端点 路径 leftrightarrow 异或 抽象 HNOI2015 权值 P3242 盘子

好吧好吧,自己做出来的第一道整体二分。

省流:理解能力比较强的话直接拖到最后看算法流程吧。

下面我们称输入时盘子的权值为“盘子的大小”,与文中使用的算法给盘子的赋权区分开。


一堆询问第 \(k_i\) 小,考虑整体二分。

先考虑外部过程。

上整体二分板子,每次二分 \(mid\),形象地把盘子集合掰成两半,左集合里的盘子满足大小都 \(\leq mid\),右集合就是剩下一半。

接下来只考虑左集合的盘子,计算出对于水果集合中第 \(i\) 个水果包含了多少个左集合中的盘子,记为 \(c_i\)。把 \(c_i\leq k_i\) 的那一部分水果随着左集合向左侧二分 \([l,mid]\),剩下的水果 \(k_i\gets k_i-c_i\) 排除掉左集合贡献之后,再随着右集合向右侧二分 \([mid+1,r]\) 即可。

当 \(l=r\) 时,直接给水果集合里的水果答案就行。

真正麻烦的其实是怎么能快速算出来每个水果包含了多少个左集合中的盘子。

考虑找出一条路径 \(u'\leftrightarrow v'\) 是母路径 \(u\leftrightarrow v\) 的子路径的充要条件,可以发现当且仅当 \(u'\) 和 \(v'\) 都在 \(u\leftrightarrow v\) 上,\(u'\leftrightarrow v'\) 才构成 \(u\leftrightarrow v\) 的子路径。那么想数出子路径数量,就是想数有多少条路径两个端点都同时在母路径上。这种两个同时存在做贡献只存在一个或者不存在都不做贡献的形式,容易想到做异或哈希。

然而你发现这很难异或哈希,因为异或哈希不能维护满足条件的路径数量,但是这启发我们使用异或并尝试使得位与位间不冲突以维护子路径数量。

我们不妨给所有盘子一个互不相同的编号 \(i\),权值设置为 \(2^i\) 并把权值挂在两个端点上,这样我们可以查询水果 \(u\leftrightarrow v\) 这一路上的权值异或和,而它的 popcount 就是水果 \(u\leftrightarrow v\) 里有多少个盘子的恰好一个端点。再做一次补集转化,用 \(u\leftrightarrow v\) 里盘子端点的总数减掉这个 popcount 再除以 \(2\),就是水果 \(u\leftrightarrow v\) 里两个端点同时都在的盘子数量。

为了降低时间复杂度,编号可以直接依次给成 \(0\sim p-1\),然后开 \(n\) 个大小为 \(p\) 的 bitset,这样每次对权值的操作(异或或者查 popcount,以及实现过程中需要做的清空等)就都是 \(\mathcal O(1)\) 或者 \(\mathcal O(\frac{p}{w})\) 的了。

现在问题转化成,每次只有左集合的那一部分盘子是有效的,怎么求一条路径上的异或和。为了保证复杂度,我们不能每一次都扫一遍整棵树,但是我们发现只有左集合盘子的端点的权值是有用的,这启发我们每一次都把左集合盘子的端点当做关键点建立虚树,建立虚树的复杂度和虚树上的节点数量都是左集合大小级别的,复杂度没有问题。

为了让虚树总是树从而方便操作,可以把根节点当做权值为 \(0\) 的关键点也加进虚树,无伤大雅。

建立虚树之后事情就简单多了,对虚树垒一波树上异或前缀和,然后把查询的水果 \(u\leftrightarrow v\) 路径的端点 \(u,v\) 等价地挪移到虚树节点上,然后直接类似树上差分,把四个 bitset 异或在一起就是水果 \(u\leftrightarrow v\) 路径在只有左集合盘子的情况下的权值异或和。

这里挪移端点是因为水果 \(u\leftrightarrow v\) 的端点 \(u,v\) 并不一定都在虚树上,但是我们只有虚树上的点是有信息的,所以我们要收缩这条路径为它的一个子路径,这条子路径需要满足两端都是虚树节点,且没有损失任何信息(在收缩过程中没有丢掉任何一个关键的虚树节点)。换句话说,这个收缩的过程就像是把左右端点分别向路径中间收缩,直到各自都收缩到一个虚树节点。这样我们原来想查的 \(u\leftrightarrow v\) 权值异或和,就可以转化成查这两个虚树节点在虚树上的路径的异或和,而这是一个简单的虚树上的树上差分。

挪移端点需要进行分类讨论,还要查询树上一段路径上有没有关键点。鉴于我们计算每个水果的总答案时还要查询一条路径上关键点的数量,但是我们每次都只需要设置一些点是关键点,使用树上差分加树状数组可以较快地解决。

有点麻烦,梳理一下算法流程:

  1. 按照输入顺序,给输入的第 \(i\) 个盘子权值 \(2^{i-1}\)。
  2. 整体二分,以 \(\leq mid\) 为盘子大小的分界线,得到盘子的左集合。
  3. 将左集合盘子的路径端点设置为关键点,建立虚树,然后把左集合盘子的权值挂到路径端点上。
  4. 对虚树垒权值的异或前缀和。
  5. 考虑水果,对于水果 \(u\leftrightarrow v\),把两个端点等价收缩到虚树上。
  6. 查询收缩后的两端点在虚树上的路径权值异或和,可以通过树上差分得到,显然这个等价于在只有左盘子集合的情况下原 \(u\leftrightarrow v\) 的路径权值异或和。
  7. 查到这个东西,再查一个 \(u\leftrightarrow v\) 路径上关键点的数量,就可以算出来这个水果包含了多少个左盘子集合里的盘子。以此再划分水果,整体二分递归下去就可以了。

对于每一次判定,建立虚树复杂度 \(\mathcal O(n'\log n)\),给虚树垒前缀异或和复杂度 \(\mathcal O(\frac{n'p}{w})\),对于每个水果计算包含盘子数量复杂度 \(\mathcal O(n' \log n+\frac{n'p}{w})\)。给盘子大小做离散化之后,整体的复杂度就应该是 \(\mathcal O(n\log^2 n+\frac{np}{w}\log n)\) 的。

这玩意算出来倒不是很抽象,但是常数很大。然而并不妨碍开了 O2 之后 bitset 快得飞起,可以在 3s 内通过,不开 O2 无法通过。总时间来说比 SA 又 assert 又不开 O2 的 \(\mathcal O(n\log ^2 n)\) 跑得快八秒(

实现的时候细节很多,要特判各种 LCA 是根节点的情况,还要写一堆板子,还有清空(清空虚树和树状数组)。但是最后想清楚了写出来还是觉得蛮清晰的。我大概调了两个小时。

代码写了 7.3K,太长了就放这里吧

AC Record

标签:端点,路径,leftrightarrow,异或,抽象,HNOI2015,权值,P3242,盘子
From: https://www.cnblogs.com/lemonniforever/p/18077195

相关文章

  • 设计模式——抽象工厂实验
    抽象工厂实验实验场景:电子商务系统中创建的订单分为国内订单(DomesticOrder)和海外订单(OverseasOrder);国内订单使用人民币支付(RMBPayment),海外订单使用美元支付(USDPayment)。实验要求:设计使用抽象工厂模式来实现订单创建功能。实验内容:将订单工厂中的接口封装为order-api......
  • C语言中抽象函数与具体实现的命名与组织
    C语言中抽象函数与具体实现的命名与组织在C语言的项目开发中,尤其是嵌入式系统和开源软件项目里,合理地命名和组织抽象函数及其具体实现对于提高代码的可读性、可维护性和可扩展性至关重要。以下是关于如何在这些项目中有效地处理抽象和实现的一些建议:抽象函数与具体实现的区分A......
  • 【Java面试题-基础知识02】Java抽象类和接口六连问?
    1、抽象类和接口分别是什么?抽象类是一种类,可以包含抽象方法和非抽象方法,抽象方法是没有具体实现的方法,需要在子类中被具体实现。接口是一种完全抽象的类,其中的所有方法都是抽象方法,没有方法体,它只是定义了一组方法的契约。2、接口中一定不可以有实现方法吗?不一定,Java8引入......
  • C++纯虚函数和抽象类
    在C++中,可以将虚函数声明为纯虚函数,语法格式为:virtual返回值类型函数名(函数参数)=0;纯虚函数没有函数体,只有函数声明,在虚函数声明的结尾加上=0,表明此函数为纯虚函数。最后的=0并不表示函数返回值为0,它只起形式上的作用,告诉编译系统“这是纯虚函数”。包含纯虚函数的类称......
  • 抽象工厂模式
    本文借助jdk中实现jdbc的原理来描述描述一下抽象工厂模式,首先定义两个抽象接口:连接接口和命令接口。interfaceIConnect{voidconnect();}interfaceICommand{voidcommand();}此时再定义一个数据库操作util用来对数据库进行抽象对数据库进行处理。interfaceIDa......
  • 写点抽象话
    组合\(\binom{n}{m}=\binom{n}{n-m}\)。\(\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\)。这两个都很基础。\(\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}\)。组合意义。二项式定理:\((x+y)^n=\sum\limits_{i=0}^n\binom{n}{i}......
  • 解密prompt系列26. 人类思考vs模型思考:抽象和发散思维
    在ChainofThought出来后,出现过许多的优化方案例如Treeofthought,GraphofThought,AlgorithmofThought等等,不过这些优化的出发点都更加"MachineLike",而非"HumanLike",哈哈不是说机器化不好,仅仅是对AGI的一些个人偏好而已。所以如果我们从人类思考的角度出发,能否把当......
  • PHP抽象类的使用
    1、定义抽象类:使用abstract关键字定义一个抽象类。抽象类中可以包含抽象方法、普通方法和属性。例如:abstractclassAnimal{protected$name;abstractpublicfunctionmakeSound();publicfunctionsetName($name){$this->name=$name;}}......
  • 04_抽象工厂模式
        抽象工厂模式是一种创建型设计模式,它提供一个接口用于创建一系列相关或相互依赖对象的工厂,而不需要指定具体的类。这种模式通过提供一个抽象的工厂接口,使得客户端可以创建一系列产品对象而无需关心具体的实现细节。    在抽象工厂模式中,通常会定义一个抽象工......
  • Java 抽象类与方法:实现安全性与代码重用
    Java内部类简介在Java中,可以嵌套类(即类内部的类),称为内部类。嵌套类的目的是将属于一起的类分组,从而使您的代码更可读和可维护。访问内部类要访问内部类,请创建外部类的对象,然后创建内部类的对象:classOuterClass{intx=10;classInnerClass{inty=5;}......