前缀极差（C语言）

蒜头君有 nn 个数，他提出了 qq 个问题，每个问题是说，询问前 xx 个数的极差（最大值减最小值）。你能帮助他解决这 qq 个问题吗？

第一行两个整数 n, q(1 leq n, q leq 10 ^ 5)n,q(1≤n,q≤105)

第二行 nn 个整数 a_i(1 leq a_i leq 10 ^ 9)ai​(1≤ai​≤109) 表示蒜头君的 nn 个数

第三行 qq 个整数 x_i(1 leq x_i leq n)xi​(1≤xi​≤n) ，表示每一次询问

输出一行，包含 qq 个整数，表示每一次询问的答案

对于 60%60% 的数据, 1 leq n, q leq 10 ^ 31≤n,q≤103

对于 100%100% 的数据，1 leq n, q leq 10 ^ 51≤n,q≤105

输出时每行末尾的多余空格，不影响答案正确性

样例输入

5 5
3 2 4 5 1
1 2 3 4 5

样例输出

0 1 2 3 4

思想：前缀和思想，每输入一个值都要在新数组中记录这个数所带来的改变（即最大最小值） 

代码：

#include
int max[10005],min[10005],a[10005];
int mx(int a,int b)//比较大小并返回较大值
{
	return (a>b)?a:b;
}
int mn(int a,int b)//比较大小并返回较小值
{
	return (a>b)?b:a;
}
int main()
{
	int n,q;
	scanf("%d %d",&n,&q);
	for(int i=0;i0){//每输入一个值记录输入该值前所有最大最小值
			max[i]=mx(max[i-1],t);
			min[i]=mn(min[i-1],t);
		}
	}
	for(int i=0;i