计算

10420: 计算

时间限制: 2 Sec 内存限制: 128 MB

题目描述

给定一个数列，第i个位置包含两个数ai，bi

每次询问给出x，y

求数列ai*x+bi*y的最大值

输入所有数为自然数，在int范围内

输入格式

第一行为n，m。n为数列长度,m为询问个数。

接下来n行，每行两个数，代表ai，bi

接下来m行，每行两个数，代表x，y

每行输出一个答案

n，m<=100000

样例输入

3 3

1 5

9 0

9 1

4 4

1 1

3 4

样例输出

　　绳命中的估值线段树！(*@ο@*):但是为什么我感觉他就是一个基于线段树的爆搜加剪枝呢..不过是减得多一点罢了（没底气..）..

应该是挺好用的，算是一个暴力算法，在意想不到的题中能拿到让你意想不到的分

　　放板子：：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<map>
 6 using namespace std;
 7 const int N=300000;
 8 int read(){
 9     int sum=0,f=1;char ch=getchar();
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
12     return sum*f;
13 }
14 long long n,m,x,y,ans;
15 int maxa[N],maxb[N],mina[N],minb[N];
16 void pushup(int rt){
17     maxa[rt]=max(maxa[rt<<1],maxa[rt<<1|1]);
18     maxb[rt]=max(maxb[rt<<1],maxb[rt<<1|1]);
19     mina[rt]=min(mina[rt<<1],mina[rt<<1|1]);
20     minb[rt]=min(minb[rt<<1],minb[rt<<1|1]);
21 }
22 void build(int l,int r,int rt){
23     if(l==r){
24         maxa[rt]=read();maxb[rt]=read();
25         mina[rt]=maxa[rt];minb[rt]=maxb[rt];
26         return;
27     }
28     int mid=(l+r)>>1;
29     build(l,mid,rt<<1);
30     build(mid+1,r,rt<<1|1);
31     pushup(rt);
32 }
33 void dfs(int rt){
34     if(maxa[rt]==mina[rt]&&maxb[rt]==minb[rt]){
35         ans=max(ans,x*maxa[rt]+y*maxb[rt]);
36         return;
37     }
38     int gg1=rt<<1,gg2=rt<<1|1;
39     long long ans1=maxa[gg1]*x+maxb[gg1]*y;
40     long long ans2=maxa[gg2]*x+maxb[gg2]*y;
41     if(ans1>ans2){
42         if(ans1>ans) dfs(gg1);
43         if(ans2>ans) dfs(gg2);
44     }
45     else{
46         if(ans2>ans)    dfs(gg2);
47         if(ans1>ans)    dfs(gg1);
48     }
49 }
50 int main(){
51     n=read();m=read();
52     build(1,n,1);
53     for(int i=1;i<=m;++i){
54         x=read();y=read();
55         ans=-0x7fffffff;dfs(1);
56         printf("%lld
",ans);
57     }
58     return 0;
59 }

可能写丑了...