[CSP-S模拟测试]:A（单调栈维护凸包+二分答案）

题目传送门（内部题150）

输入格式

　　第一行两个整数$N,Q$。
　　接下来的$N$行，每行两个整数$a_i,b_i$。
　　接下来的$Q$行，每行一个整数$x$。

输出格式

　　对于每个询问，输出一行一个整数表示答案。

样例

样例输入：

2 4
3 0
4 -2
-1
0
1
2

样例输出：

6
0
3
12

数据范围与提示

　　每个测试点$10$分，共$10$个测试点：

对于所有的数据，有：$1\leqslant N,Q,|a_i|,|b_i|,|x|<32323$。

题解

发现式子中没有$c_i$，所以可以把一个$x$提出来，于是就变成了一个一次函数，而对于$x$的正负分类讨论就好了。

对于一次函数，可以用单调栈维护凸包找位于凸包上的$a_i,b_i$，然后对于每一组询问二分答案即可。

时间复杂度：$\Theta((N+Q)\log N)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int a,b;}e[500001],S[500001],L[500001],R[500001];

int N,Q;

int top,l,r;

bool cmp1(rec a,rec b){return a.a==b.a?a.b<b.b:a.a<b.a;}

bool cmp2(rec a,rec b){return a.a==b.a?a.b>b.b:a.a<b.a;}

double ask(rec a,rec b){return(double)(a.b-b.b)/(b.a-a.a);}

int main()

{

	scanf("%d%d",&N,&Q);

	for(int i=1;i<=N;i++)scanf("%d%d",&e[i].a,&e[i].b);

	sort(e+1,e+N+1,cmp1);

	S[0].a=0x3f3f3f3f;

	for(int i=1;i<=N;i++)

	{

		while(top&&(S[top].a==e[i].a||ask(S[top],e[i])<0))top--;

		while(top>1&&ask(S[top-1],S[top])>ask(S[top],e[i]))top--;

		S[++top]=e[i];

	}

	for(int i=1;i<=top;i++)L[++l]=S[i];

	sort(e+1,e+N+1,cmp2);top=0;

	for(int i=1;i<=N;i++)

	{

		while(top&&(S[top].a==e[i].a||ask(S[top],e[i])>0))top--;

		while(top>1&&ask(S[top-1],S[top])<ask(S[top],e[i]))top--;

		S[++top]=e[i];

	}

	for(int i=1;i<=top;i++)R[++r]=S[i];

	while(Q--)

	{

		int x;scanf("%d",&x);

		if(!x){puts("0");continue;}

		if(x>0)

		{

			int lft=1,rht=l,res=1;

			while(lft<=rht)

			{

				int mid=(lft+rht)>>1;

				if(ask(L[mid-1],L[mid])<x){lft=mid+1;res=mid;}

				else rht=mid-1;

			}

			printf("%lld\n",1LL*L[res].a*x*x+L[res].b*x);

		}

		else

		{

			int lft=1,rht=r,res=1;

			while(lft<=rht)

			{

				int mid=(lft+rht)>>1;

				if(ask(R[mid-1],R[mid])<x)rht=mid-1;

				else{lft=mid+1;res=mid;}

			}

			printf("%lld\n",1LL*R[res].a*x*x+R[res].b*x);

		}

	}

	return 0;

}

rp++

巴特西