原题目名字是“我们仍未知道那天所看见的数据结构的名字”，由于原题目名太长就叫Unknown了…… 我们，渐渐地长大了。在这缓缓逝去的季节里，屏幕上闪烁的字符，也在静静地变化着。 那个季节里编写的数据结构，叫什么名字来着呢？ 慢慢地，OI渐渐地淡去。而我们则在不断成长，但是那个程序一定仍在某个时空里继续运行着。 Salroey忘了那个数据结构的名字和内容，但她却记得题目，于是她来寻求你的帮助。 有一个元素为向量的序列，下标从1开始，初始时为空，现在你需要支持三个操作： 1.在S的末尾添加一个元素(x,y)。 2.删除S的末尾元素。 3.询问下标在[l,r][l,r]区间内的元素中，(x,y)×Si的最大值。 其中××表示向量的叉积，(x1,y1)×(x2,y2)=x1y2−x2y1

由于 \(1\) 操作保证了向量一定是在 \(x\) 轴上方的 所以一定答案一定在凸包上,如果不是区间查询的话,维护一个凸包,然后三分就行了 如果有区间查询,用线段树维护就好了 对于每一个节点维护一个凸包,但是暴力合并复杂度是 \(O(n)\) 的 考虑一种神奇的做法....

由于这题点是在序列末端插入和在序列末端删除的 利用这个性质,我们可以等区间的点都满了再合并....但是可以在一个点附近反复横跳删除和添加 这样还是被卡了

所以用一个神奇的套路: 等该层的下一个节点满了再合并这个节点,这样的话,假设序列长度为 \(k\),那么每 \(k\) 次插入才会 \(O(k)\) 的合并一次,均摊是 \(O(1)\) 的....

复杂度 \(O(n*log^2)\),代码常数贼大...