题意
给出 (N) 个形如 (f_i(x)=a_ix^2+b_i) 的二次函数。
有 (Q) 次询问，每次给出一个 (x)，询问 (max(f_i(x)))。
输入格式
第一行两个整数 (N),(Q)。
接下来的 (N) 行，每行两个整数 (a_i),(b_i)。
接下来的 (Q) 行，每行一个整数 (x)。
输出格式
对于每个询问，输出一行一个整数表示答案。
input
2 4
3 0
4 -2
-1
0
1
2
output
6
0
3
12
限制与约定
每个测试点 (10) 分，共 (10) 个测试点：
对于所有的数据，有：
(1≤N,Q,|x_i|,|a_i|,|b_i|<32323)。
时间限制：1s
题解
这道题看似是数据结构，但可以离线处理。
当 (x>0) 时，要求 (a_ix^2+b_ix) 的最大值，只需要求出 (a_ix+b_i) 的最大值。
于是问题就转化为了，给定一堆直线，求在某些点的最大值。
显然答案一定在上凸壳上。
对于每组询问，只要二分出它在上凸壳的哪个位置就行。
同样的，当 (x<0) 时，答案在 (a_ix+b_i) 的下凸壳上，再写一个凸壳就行了。
时间复杂度 (O((n+q)log n))。
code
#include <bits/stdc++.h>
#define int long long
#define re register int
using namespace std;
inline void read(int &x){
x=0;char ch=getchar();bool f=0;
for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
x=f?-x:x;
}
const int N=5e5+10,M=32323;
int t,k[N],b[N],id[N],n,q,p[N],a1[M+1],a2[M+1];
inline int f(int x,int i){return k[x]*i*i+b[x]*i;}
inline int cmp(int x,int y){return (k[x]==k[y])?b[x]<b[y]:k[x]<k[y];}
inline double check(int i,int j){return 1.0*(b[j]-b[i])/(k[i]-k[j]);}
signed main(){
read(n),read(q);
for(re i=1;i<=n;++i) read(k[i]),read(b[i]),id[i]=i;
sort(id+1,id+n+1,cmp);t=0;
for(re i=1;i<=n;++i){
while(t&&k[id[i]]==k[p[t]]) --t;
while(t>1&&check(id[i],p[t])<=check(p[t],p[t-1])) --t;
p[++t]=id[i];
}
for(re i=1,j=1;i<=M;++i){
while(j<t&&f(p[j],i)<=f(p[j+1],i)) ++j;
a1[i]=f(p[j],i);
}
for(re i=1;i<=n;++i) b[i]=-b[i],p[i]=0;
sort(id+1,id+n+1,cmp);t=0;
for(re i=1;i<=n;++i){
while(t&&k[id[i]]==k[p[t]]) --t;
while(t>1&&check(id[i],p[t])<=check(p[t],p[t-1])) --t;
p[++t]=id[i];
}
for(re i=1,j=1;i<=M;++i){
while(j<t&&f(p[j],i)<=f(p[j+1],i)) ++j;
a2[i]=f(p[j],i);
}
while(q--){
int x;read(x);
if(x>0)printf("%lld
",a1[x]);
if(x==0) puts("0");
if(x<0)printf("%lld
",a2[-x]);
}
return 0;
}