icontofig | 发布于 2019-08-29 22:08:21 | 阅读量 461 | 线段树
发布于 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 | 阅读量 421 | 线段树
发布于 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 | 阅读量 298 | 线段树
发布于 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 | 阅读量 183 | 线段树 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 | 阅读量 309 | 线段树 扫描线
发布于 2019-03-12 17:13:37 | 线段树 扫描线
hdu 1542 Atlantis 扫描线:矩形面积并
题目大意给出矩形的左下端点和右上端点的坐标,求所有的矩形的面积的并。 题解求矩形面积并是扫描线的基础经典问题。这篇blog是借助这个来介绍初步入门扫描线。 扫描线,顾名思义,就是一条上下扫描或者左右扫描的虚拟的自主创造的线。 在扫描线扫描到一条线段的时候,就进行操作。而这种操作常常是利用线段树这种数据结构来进行存储的。 在矩形面积的并这一个问题中,我们可以这样去把要计算的总的面积分为这样几个部分来看: (图来自于别人的博客,实在是不想自己画图了QAQ) 我们可以看到,这个图就是按照扫描线来分区计算面积的。 我们每一次找到一条扫描线,就要维护当前在这条扫描线上(当然这里扫描线是向上扫的)所有的
继续阅读
icontofig | 发布于 2018-12-26 11:18:55 | 阅读量 504 | 线段树
发布于 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 | 阅读量 159 | 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 | 阅读量 187 | 整体二分 线段树
发布于 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的数有
继续阅读
icontofig | 发布于 2017-01-08 09:23:48 | 阅读量 359 | splay 线段树
发布于 2017-01-08 09:23:48 | splay 线段树
【ZJOI2007】【BZOJ1058】报表统计splay+线段树
题目描述小Q的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小Q希望可以帮妈妈分担一些工作,作为她的生日礼物之一。经过仔细观察,小Q发现统计一张报表实际上是维护一个可能为负数的整数数列,并且进行一些查询操作。在最开始的时候,有一个长度为N的整数序列,并且有以下三种操作: INSERT i k 在原数列的第i个元素后面添加一个新元素k; 如果原数列的第i个元素已经添加了若干元素,则添加在这些元素的最后(见下面的例子) MIN_GAP 查询相邻两个元素的之间差值(绝对值)的最小值 MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值(绝对值) 例如一开始的序列为 5 3
继续阅读