今天推一首 Postcard,出自我戳新专。

比赛地址就不放了反正大家也没有权限

这次比赛没有提供题目文件下载,不方便直接给出原题,我口胡一下题意吧。

A

题目描述

你有 $N$ 个形如 $a_i imes x^2 + b_i imes x $ 的函数,现在有 $Q$ 个询问,每个询问包含一个整数 $x_i$ ,求 $max(f_i_{x_i})$。

思路

感觉直接维护二次函数是不可行的,我们对每个函数先提出一个 $x$ 将它变为一次函数,然后在用线段树维护区间内最高(最低)的一条线段。

为了避免开两棵线段树,可以把二三两个象限的线段沿 $x$ 轴翻转,然后就是 Segment 原题了。

代码

//注意一定要输入输出优化