笛卡尔树（）

· · 算法·理论

因为明天要考，而且考得是蓝题，所以我的总结只会在蓝题上面多说几句。

【模板】笛卡尔树

P1310 [NOIP2011 普及组] 表达式的值

这道题目我当时做的很水。

我们要将这个序列转化成一棵算式树，然后我们就能用dp[i][0]表示计算到i号节点，答案为0的方法数，dp[i][1]表示计算到i号节点，答案为1的方法数。

在树上，当前节点是+和-都是有不同计算方式的。

那么时间复杂度就会卡在算式树的转换上面。

其中括号还存在优先级，这个的处理又是很麻烦的。

首先+最先运算，我们考虑给它一个较小的值，然后利用小根堆的规则建立笛卡尔树。至于为什么是笛卡尔树，一个符号的左右棵子树，刚好可以把原来的算式分成两个区间，进行计算。

如果遇到了(那么cnt ++，赋予这个括号里面的+ cnt \times 2 + 1的权值，要乘2的原因是前面的括号里面有两个可能的符号

然后建树的时候不需要括号的参与。这样做就可以了qwq。

Gardener AlexCF1220F

昨天题解区的方法抽象+恶心。初三有两位同学分享了更加简单的方法。其实就是二分找到最优的位置。每一次的check都暴力建树算深度判断。

P6453 [COCI2008-2009#4] PERIODNI

这也是一道蓝题，同样是dp。

建立一个小根堆的笛卡尔树。每次遍历到下一层节点后，直接减去上面的就可以了。当层剩下的节点就是可以选择的列数，当前节点的siz就是可以选择的行数。假设当前节点一共要选择$i$个节点，之前一共选择了$j$个节点那么方案数就是$C(a, z) * C(b - j, z) * A(x)$就可以了。 里面选择点数有很多边界的判断问题，并不能暴力的从0枚到n。另外为了避免重复的计算，我们的$dp$应该从大到小进行更新。 答案是$dp[stk[1]][k]

P3592 [POI2015] MYJ

紫色题目。难得温故。

HISTOGRA - Largest Rectangle in a Histogram

比较简单，绿色题目，现场能推。

P3246 [HNOI2016] 序列

紫色题目。有一个性质所以可以用前缀和处理O(1)更新答案。

有一个比较坑的地方就是莫队在扩展的时候先l--,r++再算其他的。不然可能会出现L > R的情况。

跟笛卡尔树的模板关系不大。

P4755 Beautiful Pair

紫色题目，可持久化线段树。当时直接复制粘贴的以前代码。

得出结论：明天会考哪两道重题简直显而易见。TQ的提示真不错。

考重题的原因是为了有一个好看的记档分。咱就说这跟我一个高一的真的没有什么关系啊啊啊。

「51NOD1934」受限制的排列

会这道题目的关键就是读懂题目。简单来说就是知道哪些是不满足条件的。然后就可以愉快分治了。

不得不说笛卡尔树的本质就是用区间最值作为断点进行分治。