【1.24每日练习】线段树+ST表

之前忘记做ST表的笔记了。

反正就是一个很简单的东西。

$st[i][j]$ 表示的是区间 $[i , i + 2^j -1]$ 的极值,区间长度是 $2^j$
很自然的有

所以主体程序是

1
2
3
4
5
6
7
8
9
10
void init() {
for (int i = 1; i <= n; i++) {
st[i][0] = b[i];
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) - 1 <= n; i++) {
st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
}
}

查询函数

1
2
3
4
5
int query(int l, int r) {
if (l > r)return 0;
int k = (int)(log(r - l + 1.0) / log(2.0));
return max(st[l][k], st[r - (1 << k) + 1][k]);
}

今天的第一题是个水题

Balanced Lineup

题目
这道题好像也是st表,hhh我用的线段树
题意

查询区间最大值和最小值的差

重写一遍,应该用st表更优

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e4 + 10;

int Min[maxn][30];
int Max[maxn][30];
int n, q;
int A[maxn];

void init() {
for (int i = 1; i <= n; i++) {
Min[i][0] = A[i];
Max[i][0] = A[i];
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) - 1 <= n; i++) {
Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
}
}
}

int query(int l, int r) {
if (l > r)return 0;
int k = (int)(log(r - l + 1.0) / log(2.0));
return max(Max[l][k], Max[r - (1 << k) + 1][k]) -
min(Min[l][k], Min[r - (1 << k) + 1][k]);
}

int main() {
scanf("%d%d", &n, &q);

for (int i = 1; i <= n; i++) {
scanf("%d", A + i);
}
init();
for (int i = 1; i <= q; i++) {
int l, r; scanf("%d%d", &l, &r);
printf("%d\n", query(l, r));
}
}

Frequent values

题意:

给一个非递减序列,查询区间内出现次数最多的数字

思路

先求出频次序列,找到查询区间【l,r】 内的第一个频次为1的 k
max(k-l,query(k,r)) 就是答案

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
50
51
52
53
54
55
56
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;

const int maxn = 2e5 + 10;

int st[maxn][30];
int a[maxn], b[maxn];

int n, q;

void init() {
for (int i = 1; i <= n; i++) {
st[i][0] = b[i];
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) - 1 <= n; i++) {
st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
}
}

int query(int l, int r) {
if (l > r)return 0;
int k = (int)(log(r - l + 1.0) / log(2.0));
return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
while (scanf("%d", &n) && n != 0) {
scanf("%d", &q);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
b[1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i] == a[i - 1]) {
b[i] = b[i - 1] + 1;
}
else {
b[i] = 1;
}
}
init();

for (int i = 1; i <= q; i++) {
int l, r; scanf("%d%d", &l, &r);
int t = l;
while (b[l] != 1 && l <= r) {
l++;
}
printf("%d\n", max(l - t, query(l, r)));
}
}
}