首页 > 其他分享 >CF1588 FJumping Through the Array

CF1588 FJumping Through the Array

时间:2023-08-04 23:55:57浏览次数:61  
标签:环上 分块 黑点 FJumping sqrt Through 序列 操作 Array

CF1588F Jumping Through the Array

题意

你有个长度为 \(n\) 的数组 \(a\) 和一个长度为 \(n\) 的排列 \(p\),对于每一个 \(i\) 有一有向边 \((i,p_i)\)。

有如下三种操作:

  • 1 l r 询问 \(\sum_{i=l}^r a_i\)。

  • 2 v x 将所有 \(v\) 能到达的节点所对应编号的值加 \(x\)。

  • 3 x y 交换 \(p_x\) 与 \(p_y\)。

对于每一 \(1\) 操作输出结果。

题解

先分析一下题目,显然这个序列抽象成图之后会变成一堆环。

首先考虑只有前两个操作的情况下怎么做。

首先这种形状的图一般数据结构不太好维护,考虑分块。
我们要找到一种方法使得每次操作只有 \(O(\sqrt{n})\) 的级别。

先分析一下操作在图上的影响。
操作二是给所在环整体加上一个数。
操作一就是原序列的值之和与环上的影响整合。

首先操作二直接给环上打 \(tag\) 即可。
操作一若直接在序列上搞不太好做,考虑从环上得到对序列的影响。
显然只有被操作过的环有贡献,也就是说环的数量是由操作次数来定的。

注意到我们可以用一次操作来将所有环上的贡献对应到序列上
所以我们可以用类似一个根号重构的方式来搞这东西。
每 \(\sqrt{n}\) 次操作将环上的贡献对应到序列上,而下一段也只会增加 \(\sqrt{n}\) 个环,中间我们只枚举操作过的环就可以做到每次操作在 \(\sqrt{n}\) 的级别。

这样就解决了没有操作三的情况。

类似的,我们可以发现操作三是将一个环分裂成两个环或者是将两个环并在一起。
若没有分裂的情况,显然可以直接套用之前的方法来解决。
若有分裂的情况就不太好办了。

考虑只有合并为什么是可行的,因为每个环的内部结构是不变的

所以同样的,我们找到每一个环中不变的地方
注意每 \(\sqrt{n}\) 段操作三至多影响到 \(2\sqrt{n}\) 个点,将这些点称作黑点,我们提前将这一段操作中的黑点预处理出来。
显然对于一个环中一个黑点往回找,一直找到上一个黑点为止,中间的白点与最开始的黑点即为不变的部分,这就把环切成了一段一段的。
我们将每一段看做一个点,我们直接嗯维护这 \(2\sqrt{n}\) 个点形成的图即可。

最后找到一段中与给定区间重合的数量可以对每一段提前排好序后二分。
这样做每次就是 \(O(\sqrt{n}logn)\),这时块长取 \(\sqrt{\frac{n}{logn}}\),可以将时间复杂度平衡至 \(O(n\sqrt{nlogn})\)。
实际上可以通过预处理去掉二分,这样时间复杂度就仍然是 \(O(n\sqrt{n})\)。

实际上这就是操作分块,将多个操作连在一起处理。

我的代码比较奇特,使用了二分,但是块长取 \(\sqrt{n}\) 才能过,而取了 \(\sqrt{\frac{n}{logn}}\) 反而过不去,比较玄学。code

...

实际上没有三操作的就是普通的分块。
但有了三操作这题才是有了灵魂。
我们通过操作分块可以提前得到后面的条件从而进行处理。

标签:环上,分块,黑点,FJumping,sqrt,Through,序列,操作,Array
From: https://www.cnblogs.com/snow-panther/p/17607309.html

相关文章

  • js Array方法
    JAVASCRIPT对象Array对象数组属性属性描述constructor返回创建数组对象的原型函数。length设置或返回数组元素的个数。prototype允许你向数组对象添加属性或方法。Array对象方法属性描述concat()连接两个或更多的数组,并返回结果。copyW......
  • 关于 array 和 &array (数组名与数组地址)
     对于数组a:在绝大多数情况下,a等价于&a[0],即数组名等于数组首元素地址(等同于数组首地址)只有两种情况例外:1. 对数组名取地址(&a),此时虽然数值上等于a,但表示含义不同,a表示首元素地址,&a表示整个数组的首地址,    因此a+1≠&a+1,具体见前篇;2. 使用sizeof时,sizeof......
  • 无涯教程-Perl - Arrays(数组)
    数组是一个变量,用于存储标量值的有序列表。数组变量前面有一个“@”符号。要引用数组的单个元素,将使用带符号名称的美元符号($),后跟方括号中的元素索引,这是使用数组变量的简单示例-#!/usr/bin/perl@ages=(25,30,40);@names=("JohnPaul","Lisa","Kumar");......
  • Uncaught TypeError: count(): Argument #1 ($value) must be of type Countable|arra
    今天在安装attachments插件时后台提示UncaughtTypeError:count():Argument#1($value)mustbeoftypeCountable|arrayin64,这个是用php8开发经常会碰到的一个错误,如何解决呢?随ytkah一起来看看这个错误是在将count()函数用于不可计数的变量或非数组时发生的。要解决这个......
  • ThroughPath
    [ABC187E]ThroughPath思路我们考虑利用dfs序将树转换成一个序列(树链剖分中的一小部分),如下图所示:图上的括号里有两个参数,第一个参数\(in_u\)就是所谓的dfs序,而后面的\(out_u\)则是这个点为根的子树中dfs序最大的点的dfs序。这两个参数对应的就是以某个点为根的......
  • Educational Codeforces Round 152 (Rated for Div. 2) D. Array Painting
    初始所有点都是蓝色的,给定一个数组,每个元素为0,1,2等值,两种操作,选定一个点花1元变红,或者选定一个为1或者2的红色点,减去一个价值,让周围的点变红,最后所有点都要变红思路:贪心,对于一个数组来说我们找寻连续的不等于0的一段,判断每一段最多所能变红的存在两种情况010,这种情况花1可以最......
  • ArrayList源码
    add方法publicArrayList(){this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}//添加元素publicbooleanadd(Ee){ensureCapacityInternal(size+1);//确保数组容量足够添加elementData[size++]=e;returntrue;}调用add方法往Array......
  • FIFO FWFT Adapter(First Word Fall Through) 预读FIFO适配器
    预读fifo修改了一下1:增加了暂停预读信号stop。修改2:考虑一种情况,在没有预取的情况下,若fifo剩余的数据长度比预取流水线长度小,且在预取完成的前后一段时间内都没有读请求,empty流水线内会产生一段"气泡"。此时若有新的数据写入fifo,预取流水线不会对这些“气泡”进行填充,如果能......
  • 集合ArrayList
    一、在集合元素均为数字的情况的使用remove1importjava.util.ArrayList;23publicclasslianxi{4publicstaticvoidmain(String[]args){5ArrayList<Integer>list=newArrayList<>();6list.add(1);7list.add(2);8......
  • 第十三节 ArrayList&学生管理系统
    1.ArrayList集合和数组的优势对比:长度可变添加数据的时候不需要考虑索引,默认将数据添加到末尾1.1ArrayList类概述什么是集合​ 提供一种存储空间可变的存储模型,存储的数据容量可以发生改变ArrayList集合的特点​ 长度可以变化,只能存储引用数据类型。泛型的使用......