前缀极差
蒜头君有 n 个数,他提出了 q 个问题,每个问题是说,询问前 x 个数的极差(最大值减最小值)。你能帮助他解决这 q 个问题吗?
输入格式
第一行两个整数 n,q(1≤n,q≤105)
第二行 n个整数 ai(1≤ai≤109)表示蒜头君的 n个数
第三行 q个整数 xi(1≤xi≤n),表示每一次询问
输出格式
输出一行,包含 q个整数,表示每一次询问的答案
数据范围对于 60%的数据, 1≤n,q≤103对于 100%的数据,1≤n,q≤105
Sample Input
5 5
3 2 4 5 1
1 2 3 4 5
Sample Output
0 1 2 3 4
emmm,前缀和练习的第一个,算是水题叭
直接记录每个前缀的最大值和最小值,算极差
#include<cstdio>
#include<iostream>
using namespace std ;
const int N = 1e5 + 100 ;
int a[N] ;
int p[N] , t[N] ;
int x[N] ;
int main()
{
int n , q ;
scanf("%d%d",&n , &q) ;
for(int i = 1 ; i <= n ; i ++)
{
scanf("%d" , &a[i]) ;
if(i == 1)
p[i] = a[i] ,t[i] = a[i] ;
else
p[i] = max(p[i-1] , a[i]) ,
t[i] = min(t[i-1] , a[i]) ;
}
for(int i = 1 ; i <= q ; i ++)
{
scanf("%d",&x[i]) ;
x[i] = p[x[i]]-t[x[i]] ;
}
for(int i = 1; i < q ; i ++)
printf("%d ",x[i]) ;
printf("%d" ,x[q]) ;
return 0 ;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)