未获得准确的时间。导致了迟到 /(ㄒoㄒ)/~~
结果错过了前面的小半节课，也是让人难受 ≧ ﹏ ≦ 。
进入正题
解题方法：
- 分块
- 倍增
- 线段树
- 并查集
本次使用分块解决，其他方法见题目中的附件。
$n$ 个城市分布在一条直线上，从 $L$ 到 $R$ 获得最大利润时 $ans = max(a_i-a_j)(L <= j < i<= R)$.
分块先把 $n$ 个城市分成 $\sqrt{n}$ 块。
赚钱有两种情况，一种是买入卖出在同一块，另一种是在两个不同的块。
所以预处理的时候就要处理出每一块中的最小价格，最大价格，以及最大利润。
每次询问的时间复杂度为 $O(\sqrt{n})$ 。
代码如下：
#include<cstdio>
#include<cmath>
#define orz(i,a,b) for (int i = a;i <= b; i++)
#define sto(i,a,b) for (int i = a;i >= b; i--)
using namespace std;
const int N = 5e5 + 5;
int n, m, a[N], s, L, R;
struct node {
int maxn/*最大值*/, minn/*最小值*/, max_v/*块内最大收益*/;
}b[N];
void chushi(int n, int s) {//初始化
sto (i, n/s, 0)
b[i].minn = 1e9 + 9;
orz (i, 1, n) {
if (a[i] - b[i / s].minn > b[i / s].max_v)
b[i / s].max_v = a[i] - b[i / s].minn;
if (a[i] < b[i / s].minn)
b[i / s].minn = a[i];
if (a[i] > b[i / s].maxn)
b[i / s].maxn = a[i];
}
}
int main() {
scanf ("%d%d", &n, &m);
orz (i, 1, n)
scanf ("%d", a + i);
s = sqrt(n);
chushi(n, s);
while (m--) {
scanf ("%d%d", &L, &R);
int ql = L / s, qr = R / s, ans = 0;
if (ql == qr) {//买卖在同一块中
int minn = 1e9;
orz (i, L, R) {
if (a[i] - minn > ans)
ans = a[i] - minn;
if (a[i] < minn)
minn = a[i];
}
}
else {
int minn = 1e9;
orz (i, L, (ql + 1) * s - 1) {
if (a[i] - minn > ans)
ans = a[i] - minn;
if (a[i] < minn)
minn = a[i];
}
orz (i, ql + 1, qr - 1) {
if (b[i].max_v > ans)
ans = b[i].max_v;
if (b[i].maxn - minn > ans)
ans = b[i].maxn - minn;
if (b[i].minn < minn)
minn = b[i].minn;
}
orz (i, qr * s, R) {
if (a[i] - minn > ans)
ans = a[i] - minn;
if (a[i] < minn)
minn = a[i];
}
}
printf ("%d\n", ans);
}
return 0;
}