icontofig | 发布于 2020-03-04 13:04:20 | 阅读量 514 | 点分治 线段树
发布于 2020-03-04 13:04:20 | 点分治 线段树
CodeForces 1303G. Sum of Prefix Sums 点分治+李超线段树
题目大意定义一种叫做前缀数组和的东西sum_i为某个数组的前缀和数组的前i项之和。 现在给定一个树,树上每个节点有权值,树上一条有向路径的权值定义为从起点u到终点v上的所有数字组成的前缀数组和。 求问这种路径权值的最大值是多少。 题解此题解为搬运CodeForces官方题解,为其中文翻译版本。(严正声明,可能中间会加一些个人的理解,代码的话个人的代码感觉还不如官方的好看所以就放官方的题解代码了) 首先确认这是一个树上路径问题,针对树上路径问题,一般可用的方法就是树分治和树链剖分。 考虑到这道题的路径权值的定义,我们并不能用树链剖分的传统的LCA和线段树的方法来进行计算,我们大概需要用搜索算法才
继续阅读
icontofig | 发布于 2020-02-24 15:52:01 | 阅读量 426 | 线段树
发布于 2020-02-24 15:52:01 | 线段树
CodeForces 1313.C2 Skyscrapers(hard version) nlogn线段树做法
 题目大意给定一个序列a,要求你每个元素都选出不超过ai的值,使得选出的元素序列满足不严格上凸(上凸、非严格单调皆可),且总和最大,求问每个位置上选出的元素是多少。 题解此题有一个暴力的easy version版本,只需要枚举每个位置为最大值点位置pos(也就是该点处选择的元素大小为apos)暴力计算即可。 但是当数据量变大到5*105数量级时,我们没有办法枚举位置暴力计算。 但是可以注意到,枚举每个位置为最大值点位置pos这一步仍然是不可避免地,这是解题的核心,于是很容易想到,我们需要在较短时间内算出当每个位置为最大值点位置时,所选出的最优序列的元素大小总和。我们不能用暴力的版本每
继续阅读
icontofig | 发布于 2019-08-29 22:08:21 | 阅读量 525 | 线段树
发布于 2019-08-29 22:08:21 | 线段树
2018 ICPC 徐州赛站网络赛 H Ryuji doesn't want to study 线段树
题目大意给定一个序列,有两个操作: 1.询问l---r之间所有数按题目中格式公式的计算求和。 2.更改序列某个位置的值。 题解其实这题还是蛮简单的……我零基础的队友30s就像出来了(比我快了一些) 这题直接维护区间和是不行的,我们看到询问的操作中的公式跟数的位置和询问区间长度都有关系。 那么我们现在要想的就是如何让区间和与数的位置变成无关的式子。 注意到对于位置 i,有n - i + 1 - n - r,即为我们要求的区间中 位置 i的数字对应的位置系数。 所以我们可以用线段树维护两个值,一个表示 a[i]*(n-i+1)的和,另一个表示a[i]的和。 询问的时候用前一个值对应的区间询问减去后
继续阅读
icontofig | 发布于 2019-08-27 15:38:01 | 阅读量 446 | 线段树
发布于 2019-08-27 15:38:01 | 线段树
2018-2019 ACM-ICPC, Asia Shenyang Regional Contest E.The Kouga Ninja Scrolls 曼哈顿距离转换契比雪夫距离 + 线段树单点修改
题目大意有n个人,他们分别位于(x,y),属于家族c。 现在有三种操作: 1.编号为k的人位置变换到(x+xk,y+yk)。 2.编号为k的人转投到家族c。 3.查询编号区间l----r之间的所有人中两个最远的不同家族的人之间的曼哈顿距离是多少。 题解如果会曼哈顿距离转化为契比雪夫距离的话,这题思路并不难,可能就是写起来麻烦,极度锻炼思维和代码能力的一道线段树题目。 首先我们看一下曼哈顿距离去掉绝对值之后,一共只有四种情况: 1.x - x' + y - y' 2.x - x' + y' - y 3.x' - x + y - y' 4.x' - x + y' - y; 根据这四种情况,我们变换
继续阅读
icontofig | 发布于 2019-08-08 13:50:48 | 阅读量 316 | 线段树
发布于 2019-08-08 13:50:48 | 线段树
2019 Multi-University Training Contest 6 1005 Snowy Smile 线段树维护最大子段和
题目大意平面直角坐标系上有n个点,每个点有wi的价值,你可以选出一个矩形,获得矩形内部和边界上所有点的价值总和,求问最大的价值总和是多少。 题解一开始一看,这题简单啊,直接离散化上二维前缀和好了。 然后写着写着发现不对劲,二维前缀和枚举是O(n^4)的。。。 然后后面想到了其实也就是离散化后维护最大子矩阵和,大概是要用二维线段树维护的……不过这个代码难度和复杂度就…… 最后是队友给了思路:把问题通过一系列手法降维处理,把最大子段和转化为最大子区间和,这样就可以用一维的普通线段树去维护了。 首先还是要离散化,然后对于所有点按离散化后的x坐标从小到大排序。 然后我们枚举一个左侧的边界作为起始,枚举
继续阅读
icontofig | 发布于 2019-07-04 14:41:30 | 阅读量 261 | 线段树 DP BFS
发布于 2019-07-04 14:41:30 | 线段树 DP BFS
BZOJ 1999 树网的核[数据加强版] 树的直径+线段树
题解此题原本是NOIP提高组一道压轴,这一改数据感觉可以放省选赛或者CCPC难题里面什么的了 鬼知道为什么我当初做这道题会YY出线段树做法,现在想想我自己都佩服我自己。 嘛写这篇算是权当复习一下思路了。 题目告诉我们最小偏心距是什么了……我们要求的就是选定一个长度不超过s的核(在直径上,也可以是点也可以是边)使得离这个核最远的点离这个核 的距离最小。 首先求直径是很好求的,两遍BFS就搞定了。 但是直径可能会有很多条,那我们就对每一条都要计算。 对于每一条直径,我们的答案一定是由两类值的最大值来组成: 1.非此直径上的点到当前选定的核的距离的最大值。 2.直径的两个端点到当前选定的核的距离的最
继续阅读
icontofig | 发布于 2019-03-12 17:13:37 | 阅读量 358 | 线段树 扫描线
发布于 2019-03-12 17:13:37 | 线段树 扫描线
hdu 1542 Atlantis 扫描线:矩形面积并
题目大意给出矩形的左下端点和右上端点的坐标,求所有的矩形的面积的并。 题解求矩形面积并是扫描线的基础经典问题。这篇blog是借助这个来介绍初步入门扫描线。 扫描线,顾名思义,就是一条上下扫描或者左右扫描的虚拟的自主创造的线。 在扫描线扫描到一条线段的时候,就进行操作。而这种操作常常是利用线段树这种数据结构来进行存储的。 在矩形面积的并这一个问题中,我们可以这样去把要计算的总的面积分为这样几个部分来看: (图来自于别人的博客,实在是不想自己画图了QAQ) 我们可以看到,这个图就是按照扫描线来分区计算面积的。 我们每一次找到一条扫描线,就要维护当前在这条扫描线上(当然这里扫描线是向上扫的)所有的
继续阅读
icontofig | 发布于 2018-12-26 11:18:55 | 阅读量 518 | 线段树
发布于 2018-12-26 11:18:55 | 线段树
Codeforces Round#528 div2F. Rock-Paper-Scissors Championtime limit:per test 2 secondsmemory limit:per test 256 megabytesinput:standard inputoutput:standard output n players are going to play a rock-paper-scissors tournament. As you probably know, in a one-on-one match of rock-paper-scissors, two pla
继续阅读
icontofig | 发布于 2017-04-06 00:00:14 | 阅读量 197 | splay 线段树 树套树
发布于 2017-04-06 00:00:14 | splay 线段树 树套树
引言好久没写题解了,正好不怎么想写代码,还是来发波题解吧。 Description您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:1.查询k在区间内的排名2.查询区间内排名为k的值3.修改某一位值上的数值4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)5.查询k在区间内的后继(后继定义为大于x,且最小的数) Input第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数,表示有序序列下面有m行,opt表示操作标号若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名若opt=2 则为操作2,之后有三个数l,
继续阅读
icontofig | 发布于 2017-01-15 14:31:30 | 阅读量 205 | 整体二分 线段树
发布于 2017-01-15 14:31:30 | 整体二分 线段树
Description有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。 Input第一行N,M 接下来M行,每行形如1 a b c或2 a b c Output输出每个询问的结果 Sample Input2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3 Sample Output1 2 1 HINT【样例说明】第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1的数有
继续阅读