题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
输入格式
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。
第二行为m个数,分别是账目的钱数
后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。
输出格式
输出文件中为每个问题的答案。具体查看样例。
输入输出样例
输入 #1复制
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10
输出 #1复制
2 3 1
题解
这是一道线段树的模板题目。我参考的线段树模板来自：https://baijiahao.baidu.com/s?id=1605870136961096251&wfr=spider&for=pc。原来的模板是线段区间求和，现在改为区间求最小值。
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#define ll long long const int MAXN = ; using namespace std; ll n, m, a[MAXN], ans[MAXN<<], tag[MAXN<<]; ll ls(ll x)
{
return x<<;
} ll rs(ll x)
{
return x<<|;
} void push_up(ll p)
{
ans[p] = min(ans[ls(p)], ans[rs(p)]);
} void build(ll p, ll l, ll r)
{
tag[p] = ;
if(l == r)
{
ans[p] = a[l];
return;
}
ll mid = (l + r) >> ;
build(ls(p), l, mid);
build(rs(p), mid + , r);
push_up(p);
} void f(ll p, ll l, ll r, ll k)
{
tag[p] = tag[p] + k;
ans[p] = ans[p] + k * (r - l + );
} void push_down(ll p, ll l, ll r)
{
ll mid = (l + r)>>;
f(ls(p), l, mid, tag[p]);
f(rs(p), mid + , r, tag[p]);
tag[p] = ;
} ll query(ll q_x, ll q_y, ll l, ll r, ll p)
{
ll res = ;
if(q_x <= l && r <= q_y)
{
return ans[p];
}
ll mid = (l + r)>>;
push_down(p, l, r);
if(q_x <= mid)
{
res = min(res, query(q_x, q_y, l, mid, ls(p)));
}
if(q_y > mid)
{
res = min(res, query(q_x, q_y, mid + , r, rs(p)));
}
return res;
} int main()
{
ll e, f;
scanf("%lld%lld", &n, &m);
for(ll i = ; i <= n; i++)
{
scanf("%lld", &a[i]);
}
build(, , n);
for(ll i = ; i <= m; i++)
{
scanf("%lld%lld", &e, &f);
printf("%lld ", query(e, f, , n, ));
}
return ;
}