codevs3304 水果姐逛水果街Ⅰ
2024-08-31 12:35:41
题目描述 Description
水果姐今天心情不错,来到了水果街。
水果街有n家水果店,呈直线结构,编号为1~n,每家店能买水果也能卖水果,并且同一家店卖与买的价格一样。
学过oi的水果姐迅速发现了一个赚钱的方法:在某家水果店买一个水果,再到另外一家店卖出去,赚差价。
就在水果姐窃喜的时候,cgh突然出现,他为了为难水果姐,给出m个问题,每个问题要求水果姐从第x家店出发到第y家店,途中只能选一家店买一个水果,然后选一家店(可以是同一家店,但不能往回走)卖出去,求每个问题中最多可以赚多少钱。
输入描述 Input Description
第一行n,表示有n家店
下来n个正整数,表示每家店一个苹果的价格。
下来一个整数m,表示下来有m个询问。
下来有m行,每行两个整数x和y,表示从第x家店出发到第y家店。
输出描述 Output Description
有m行。
每行对应一个询问,一个整数,表示面对cgh的每次询问,水果姐最多可以赚到多少钱。
样例输入 Sample Input
10
2 8 15 1 10 5 19 19 3 5
4
6 6
2 8
2 2
6 3
样例输出 Sample Output
0
18
0
14
数据范围及提示 Data Size & Hint
0<=苹果的价格<=10^8
0<n,m<=200000
———————————————————————————
这道题可以用线段树写
线段树维护的信息有区间mx 区间mn
区间从左往右走的答案(l,r) 以及从右往左的答案(r,l)
具体合并方式看代码咯
不过注意询问的时候 因为我们是把询问拆成若干个区间的信息合并起来得到的答案
所以要有一起奇怪的处理(合并的信息太多
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=<<;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,q,v[M],L,R,ptr;
struct node{int mx,mn,lr,rl;}tr[M*+];
void up(int x,int l,int r){
tr[x].mx=max(tr[l].mx,tr[r].mx);
tr[x].mn=min(tr[l].mn,tr[r].mn);
tr[x].lr=max(max(tr[l].lr,tr[r].lr),tr[r].mx-tr[l].mn);
tr[x].rl=max(max(tr[l].rl,tr[r].rl),tr[l].mx-tr[r].mn);
}
void up(int x){up(x,x<<,x<<^);}
void build(int x,int l,int r){
if(l==r){
tr[x].mx=tr[x].mn=v[l];
tr[x].lr=tr[x].rl=;
return ;
}
int mid=(l+r)>>;
build(x<<,l,mid);
build(x<<^,mid+,r);
up(x);
}
int push_max(int x,int l,int r){
if(L<=l&&r<=R) return x;
int mid=(l+r)>>;
if(R<=mid) return push_max(x<<,l,mid);
if(L>mid) return push_max(x<<^,mid+,r);
int w=++ptr;
up(w,push_max(x<<,l,mid),push_max(x<<^,mid+,r));
return w;
}
int main(){
n=read();
for(int i=;i<=n;i++) v[i]=read();
build(,,n);
q=read();
for(int i=;i<=q;i++){
L=read(); R=read();
ptr=M*+;
bool d=;
if(L>R)std::swap(L,R),d=;
int w=push_max(,,n);
printf("%d\n",d?tr[w].rl:tr[w].lr);
}
return ;
}
最新文章
- SSM的各个配置文件
- linux安装软件通常会做哪些事
- java基础学习05(面向对象基础01)
- R 报错:package ‘***’ is not available (for R version ****) 的解决方案
- (图 BFS)走迷宫
- Android开发之通过反射获取到挂断电话的API
- Jetty实战之 安装 运行 部署
- vector -1
- Jquery中的$().each,$.each的区别
- Interlocked原子函数陷阱
- 使用Docker安装Mysql
- C# -- 使用 Task 执行多线程任务
- CRMEB系统开发文档
- queue之#单向消息队列
- 20145203盖泽双《网络对抗技术》实践五:MSF基础应用
- USB接口案例——多态和转型
- 怎样从外网访问内网IIS?
- Java Web(四) 一次性验证码的代码实现
- csu 1598(KMP)
- 使用 dataview 组件制作一览表