首页 > 其他分享 >P3242 接水果 题解

P3242 接水果 题解

时间:2024-07-18 12:19:02浏览次数:12  
标签:水果 le log 题解 线段 区间 dfn text P3242

Statement

树,给 \(m\) 条带权路径 \((a,b,v)\),\(q\) 次询问包含 \((u,v)\) 的路径中的第 \(k\) 小权值.

Solution

好题!这篇题解延伸出了很多东西。

首先路径的包含关系转为矩形(二维限制关系)是比较显然的.

具体地,\((u,v)\) 包含 \((a,b)\) 有两种情况:

  • \(u,v\) 无祖先关系:\(a\) 在 \(u\) 子树内,且 \(b\) 在 \(v\) 子树内,写出来就是 \(\text{dfn}(u)\le\text{dfn}(a)\le\text{dfn}(u)+\text{siz}(u)-1\) 且 \(\text{dfn}(v)\le\text{dfn}(b)\le\text{dfn}(v)+\text{siz}(v)-1\).
  • \(u,v\) 有祖先关系:设 \(u\) 为 \(v\) 祖先,\(w\) 为 \(u\to v\) 路径上的第二个点(\(u\) 向 \(v\) 方向的第一个儿子),则有 \(a\) 在 \(v\) 子树内,且 \(b\) 在 \(w\) 子树外,写出来:\(\text{dfn}(v)\le\text{dfn}(a)\le\text{dfn}(v)+\text{siz}(v)-1\) 且 \(1\le\text{dfn}(b)\le\text{dfn}(w)-1\) 或 \(\text{dfn}(w)+\text{siz}(w)\le\text{dfn}(b)\le n\).

注意到这样的 \((a,b)\) 的取值范围就是矩形,第二种情况是两个矩形,然后这是一步转化.

然后现在是 \((u,v)\) 被包含,也即问题变成了求包含一个点的权值第 \(k\) 小矩形.

这怎么做呢,一种显然的方法是整体二分:一次二分 \(x\) 就把所有权值 \(\le x\) 的矩形加入,判断这个点被包含了多少次.


那如果我把题改成强制在线怎么办呢!!!

先不考虑强制在线,我们可以把每个询问点离线下来排序,问题变成了需要支持区间插入一个数、区间删除一个数、单点查第 \(k\) 大.

一看就很树套树,那假装我们使用外层线段树、内层平衡树,考虑标记永久化,发现是三 log 的.

具体地,对于区间插入,我们找到外层线段树上 \(\log\) 个点,对这 \(\log\) 个点进行插入,删除类似. 这样他们儿子没有应用到这些更新,怎么办呢,你查一个叶子时,找出它以及它的所有 \(\log\) 个祖先,对这 \(\log\) 棵平衡树求他们并起来的第 k 大.

众所周知,这只能最外层二分、用排名之和判定来做(二逼平衡树),这样修改是双 log、查一次是三只 log 的,甚至不如整体二分!!!

怎么办呢,我们发现问题在于多棵平衡树无法一起二分,那我们改成外层线段树、内层权值线段树.

这样,还是同样地标记永久化,对于区间插入,对内层 \(\log\) 棵权值线段树进行单点加,区间删除类似;对于单点查,我们同样地拎出根到叶子路径上 \(\log\) 棵权值线段树,发现这时就可以多棵权值线段树一起二分了,复杂度降为双 log.(也可参考二逼平衡树的多种做法的对比)

这样我们就做完了离线问题,那强制在线怎么办呢?

发现直接持久化一下就行了,(可持久化树套树,参考 bzoj3489),时间并未增加,空间升为双 log.

具体怎么做呢,假如我们已经可以持久化了,那我们把扫描线的过程持久下来,在线询问直接在对应版本询问即可;

发现外层持久化是容易的(只维护内层线段树的根),而外层复制一次节点,内层线段树肯定不能全部复制,发现因为是单点修改,还是只复制发生更改的节点即可,然后做完了.


那如果是区间插入、区间删除、区间查第 k 小,可以离线,怎么办呢!!!

发现外层线段树区间查询,经过的点数是 \(\log\) 级别的,然后把这些点拿出来一起二分就行了.

强制在线是一样的,复杂度都没有增加.


那我们回归到原问题,我常数太大了怎么办!!!

尝试把外层线段树改成树状数组,区间插入、删除可以转化为前缀插入、删除,单点查可以变成两段前缀相减得到的树的 kth,这同样是单 log 的.

发现这样可以扩展到区间查询.

然后树状数组理论上是可以持久化的……


当然还有其他各种做法,比如 K-D Tree,树上莫队 + 值域分块等等。

总结:一道题的价值不仅在于过掉它,更是在于要总结方法、结论、trick 和规律,完善你的思考、思维方式,更好的是你通过这道题进行延伸、温故而知新,比如想他的加强版可不可以这样做,如果不行还能怎样做,这样就可以自己出题目,可以为师矣!

标签:水果,le,log,题解,线段,区间,dfn,text,P3242
From: https://www.cnblogs.com/laijinyi/p/18309274

相关文章

  • P1912 [NOI2009] 诗人小G 题解
    我们设\(s_i\)表示前\(i\)个句子的长度之和,这样就有dp\[f_i=\min_{j<i}\big\{f_j+|s_i-s_j+i-j-1-L|^P\big\}\]我们设\(w(l,r)=|s_r-s_l+r-l-1-L|^P\),如果\(w\)满足四边形不等式,则原dp具有决策单调性。设\(u=(s_i+i)-(s_j+......
  • [题解]P1452 【模板】旋转卡壳 | [USACO03FALL] Beauty Contest G
    P1452【模板】旋转卡壳|[USACO03FALL]BeautyContestG旋转卡壳模板题。凸包用的是Andrew算法,就不详述了,具体可以查查资料了解,但提一嘴Andrew算法的一些细节问题:Andrew算法的一些细节Andrew算法的模板代码如下:sort(a+1,a+1+n,cmp);st[++top]=1;for(inti=2;i<=n;i++){ ......
  • 【数学建模】——多领域资源优化中的创新应用-六大经典问题解答
    目录题目1:截取条材题目 1.1问题描述1.2数学模型1.3求解1.4解答题目2:商店进货销售计划题目2.1问题描述2.2数学模型2.3求解2.4解答题目3:货船装载问题题目3.1问题重述 3.2数学模型3.3求解3.4解答题目4:城市消防站选址问题 题目4.1问题重述4.2......
  • 题解:P10733 [NOISG2019 Prelim] Lost Array
    题解:P10733[NOISG2019Prelim]LostArray思路对于任意\(\min(X_{A_{i}},X_{B_{i}})=C_{i}\)。只要让\(X_{A_{i}}\)与\(C_{i}\)取\(\max\)值。\(X_{B_{i}}\)与\(C_{i}\)取\(\max\)值。这样可以让\(\min(X_{A_{i}},X_{B_{i}})\)绝对是\(C_{i}\)。对于为赋值......
  • 题解:P10781 【MX-J1-T1】『FLA - III』Spectral
    本题的主要思路就是数学。首先,让我们先来打一个表。\(i\)\(1\)\(2\)\(3\)\(4\)\(\dots\)\(T_{i}\)\(k\)\(1.5k\)\(1.5k\)\(1.375k\)\(\dots\)易用肉眼看见,自\(T_{3}\)之后数越来越小,于是我们大胆猜测,若\(n\ne1\),则它的最大值是\(1.5k\)否则\(k\)。......
  • 题解 P1031 [NOIP2002 提高组] 均分纸牌
    link贪心题中描述每一堆牌只能移动若干张牌到相邻的牌堆上确定了局部最优解必定能推导出全局最优解。易知均分完后,每堆牌的数量都为纸牌总数的平均数\(\mathrm{arg}\)。所以我们可以预处理每堆牌跟\(\mathrm{arg}\)的差距for(inti=1;i<=n;++i)sum+=a[i];......
  • [题解]POJ3675 Telescope——求多边形与圆相交部分的面积
    POJ3675Telescope题意简述多测。每次给定一个\(N\)边形(保证相邻输入的顶点在多边形上也是邻接的),再给定一个以\((0,0)\)为圆心,半径为\(r\)的圆。请计算出多边形和圆相交部分的面积(保留\(2\)位小数)。\(3\leN\le50\)\(0.1\ler\le1000\)\(-1000\lex_i,y_i\le1000\)。......
  • ABC361-D题解
    背景保佑LC能来一中。题意给你一个长度为\(n\)的初始字符串和目标字符串,都由W和B两种字符构成。现在初始字符串末尾接有两个空格字符,每次你可以在该字符串中选出连续两个非空格字符,并把它们按顺序与两个空格交换位置。问最少需要几步能得到目标字符串。分析首先如果两......
  • ABC361-C题解
    背景昨天打比赛的时候查了中考分,心快停跳了。题意从\(n\)个数字中删除\(k\)个数字,问剩下的数字中极差的最小值。分析首先把这\(n\)个数字排序,然后问题就可以转化为求这\(n\)个数字中所有长度为\(n-k\)的连续子段的极差的最小值。采用尺取法,可以从\(1\)开始枚举......
  • 题解:AT_abc360_c [ABC360C] Move It
    背景机房大佬掉大分了,乐悲。题意给你几个箱子和每个箱子里装有的东西\(a\)和对应的重量\(w\),现在要让每个箱子里都装有一个东西,每次可以移动任意一个箱子中的任意一个东西,代价为它的重量,问最小代价。分析贪心。首先最终状态里所有箱子一定只有一个东西,那么对于所有装东西......