POJ3264 - Balanced Lineup

2017/03/05

题目

离线求极差。

貌似可以把询问分段之后 解决?

不管了,反正是为了学 ST表。

代码

ST表 预处理复杂度是 ,对于在线询问是 的。

  1. 主要是一种倍增思想预处理 F[i][j] 表示从 i 开始,到 i + 2^j - 1 的闭区间上的值。
  2. 在线询问是将一个区间 [L, R] 上的询问分配到两个 2 的幂次长度有重叠的区间上。

缺点就是要求区间合并是单调的(例如 min, max),这样不会因为区间重叠导致炸掉。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAX_N = 50000 << 1;
int N, Q;
int src[MAX_N];
int fmax[MAX_N][20];
int fmin[MAX_N][20];
int log[MAX_N];

int qmax(int L, int R) {
//  cout << "Q[" << L << ", " << R << "] \\equiv ";
    int k = log[R - L + 1];
//  cout << "Q[" << L << ", " << L + (1 << k) - 1 << "] +";
//  cout << "Q[" << R - (1 << k) + 1 << ", " << R << "] \n";
    return max(fmax[L][k], fmax[R - (1 << k) + 1][k]);
}

int qmin(int L, int R) {
    int k = log[R - L + 1];
    return min(fmin[L][k], fmin[R - (1 << k) + 1][k]);
}

int main() {
    scanf("%d %d", &N, &Q);

    log[0] = -1;
    for(int i=1;i<=N;i++) {
        scanf("%d", &src[i]);
        fmax[i][0] = fmin[i][0] = src[i];
        log[i] = (i & (-i)) == i ? log[i-1] + 1 : log[i-1];
    }

    for(int j=1;j<=log[N];j++) {
        int c = (1 << j) - 1;
        for(int i=1;i+c<=N;i++) {
            fmax[i][j] = max(fmax[i][j-1], fmax[i + (1 << (j-1))][j-1]);
            fmin[i][j] = min(fmin[i][j-1], fmin[i + (1 << (j-1))][j-1]);
        }
    }

    int l, r;
    for(int i=0;i<Q;i++) {
        scanf("%d %d", &l, &r);
        printf("%d\n", qmax(l, r) - qmin(l, r));
    }
}